Assume quick sort uses median-of-three pivot selection and sorts the following a
ID: 3698049 • Letter: A
Question
Assume quick sort uses median-of-three pivot selection and sorts the following array in increasing order. Demonstrate how the list of values below is changed by showing the three steps below for the initial call of recursive quick sort algorithm. Put *stars* around numbers you're asked to identify. Pivot Selection: Identify the values that are used and show the changes due to pivot selection. Partition the List: Show each successive swap as the list is partitioned. Pivot Placement: Move the pivot to its final location and identify the pivot. Assume an array has N elements all containing the same value. Give the time complexity in big-O notation for sorting this array using the quick sort algorithm as specified in the readings.Explanation / Answer
33 35 90 19 66 50 39 88 25 17 61 22 87
1. Pivot selection
In Quick sort we can make the first element as pivot while beginning of quick sort so firstly Pivot would be:
*33* 35 90 19 66 50 39 88 25 17 61 22 87
33 - left
87 - right
so Pivot (left) is compared to right so if pivot 33 < right .. Yes !! no change
33 90 19 66 50 39 88 25 17 61 22 87
Now pivot (33) < 22 .. No !! swap them
22 90 19 66 50 39 88 25 17 61 33 87
Likeways Pivot is swapped to right now
22 90 19 66 50 39 88 25 17 61 *33* 87
Partition List :
While comparison and swap process pivot from left and right are compared and sorted in few steps so that partition is found when pivot = (left=right)- till same number. PFB description
now 33 is comared from left 22 and then with 90 and swapped and 33 from right till left becomes equal to right
22 33 19 66 50 39 88 25 17 61 90 87
22 33 19 66 50 39 88 25 17 61 90 87
22 17 19 66 50 39 88 25 33 61 90 87
22 17 19 33 50 39 88 25 66 61 90 87
22 17 19 25 50 39 88 33 66 61 90 87
22 17 19 25 33 39 88 50 66 61 90 87
22 17 19 25 33 39 **** (partition the list found) 88 50 66 61 90 87
3. Pivot Placement is found when we find the partition list so here the pivot is 88 in right and 22 in left lane
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.