need help with sorting in java Directions Problem 1 : Write (using pen-and-paper
ID: 3808325 • Letter: N
Question
need help with sorting in java
Directions
Problem 1: Write (using pen-and-paper rather than code) the list after each pass of quick and merge sort for the following list of numbers. Assume that you are sorting the numbers into ascending order. For quick sort, assume that the first number from the sublist is chosen as the pivot.
54 17 21 18 4 7 19 41 -> need a quick sort merge of these numbers and a merge sort two different styles. please show each pass. (2 different lists)
Problem 2: Write the list after each pass of the quick sort algorithm for the following list of numbers, using the following pivot selection strategies: first value of the sublist, middle (not median) value of the sublist, and the median of the first, middle, and last values. Assume you are sorting the numbers into ascending order. For example, in the first pass of the algorithm on these numbers, the first pivot selection strategy chooses 54, the middle strategy chooses 18 (because 18 and 4 are in the middle of the list; when the list is of even length, we can just choose to go with the first of the two middle values), and the median of the first, last and middle values chooses 41 as the pivot value, because 41 is the median of 54, 18 and 41. Repeat the above for this list of numbers. Remember that you are sorting into ascending order.
92 47 29 22 21 20 16 14 -> need a quick sort list of these numbers for each pass. (please show each pass)
Explanation / Answer
problem 1:
Quicksort pivot = 54
get the pivot element such that the element to its left are smaller and elements to the right are greater.
Then divide the list into sublist 1 ,pivot element and sublist 2
Start comparing the initial pivot element 54 from the end and swap if any element is smaller than pivot by decreasing the index
54 17 21 18 4 7 19 41 [ 54 > 41 so swap]
41 17 21 18 4 7 19 54 [41 > 19 so swap]
19 17 21 18 4 7 41 54 [19 > 7 so swap]
7 17 21 18 4 19 41 54 [7 > 4 so swap]
4 17 21 18 7 19 41 54 [17 > 7 so swap]
4 7 21 18 17 19 41 54
4 7 17 18 21 19 41 54
[All elements to the left of 19 are smaller than and elements on right side are greater than 19 , so make sublists]
4 7 17 18 19 21 41 54
[4 7 17 18] 19 [21 41 54] ( 2 sublist and pivot element)
apply quicksort on sublists
sublists are already sorted so merge them
4 7 17 18 19 21 41 54
MergeSort
54 17 21 18 4 7 19 41
start = 54 , end = 41
if start < end
if not swap them
41 17 21 18 4 7 19 54
divide the list into 2 parts
[41 17 21 18] [4 7 19 54]
start1 = 41 and end1 = 18 start2 = 4 end2 = 54
start1>end1 so swap
[18 17 21 41] [ 4 7 19 54]
divide further
[18 17][21 41] [4 7 ] [19 54]
comparing two values inside sublists
[17 18] [ 21 41] [4 7] [ 19 54]
Now merge them
[17 18 21 41] [ 4 7 19 54]
again merging
[4 7 17 18 19 21 41 54]
Problem 2:
92 47 29 22 21 20 16 14
pivot = 92
14 47 29 22 21 20 16 92
14 47 29 22 21 20 16 92
14 16 29 22 21 20 47 92
14 16 29 22 21 20 47 92
14 16 20 22 21 29 47 92
20 is the pivot element such that values left of 20 are smaller and values to the right are greater
so divide the list
[14 16] 20 [ 22 21 29 47 92]
[ 22 21 29 47 92]
22 is the pivot element here in sublist
swap 22 and 21
[21 22 29 47 92]
merge the sublists an pivot element
14 16 20 21 22 29 47 92
92 47 29 22 21 20 16 14
pivot = 21(middle and median)
21 47 29 22 92 20 16 14
21 47 29 22 14 20 16 92
21 47 29 22 14 20 16 92
14 47 29 22 16 21 20 92
14 16 29 22 47 21 20 92
14 21 29 22 47 20 16 92
14 21 29 22 47 20 16 92
14 16 29 22 47 20 21 92
14 16 29 22 21 20 47 92
14 16 29 22 20 21 47 92
14 16 29 22 20 21 47 92
14 16 20 22 29 21 47 92
29 is the pivot element
[14 16 20 22 21] 29 [ 47 92]
[14 16 20 22 21]
[14 16] 20 [ 21 22]
merge
[14 16 20 21 22]
merge
14 16 20 21 22 29 47 92
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.