Quicksort - Trouble identifying pivot

Question

I'm trying to understand quicksort and I get the general idea, but I'm having trouble with the below question. Is there an easy way to identify which pivot is being used based on the array after each iteration?

Consider the following array and its state after iterations of QuickSort on the array: 

Initial Array: 32, 12, 17, 73, 40, 88, 16, 75 
After Iter 1: 32, 12, 17, 40, 16, 73, 88, 75 
After Iter 2: 12, 16, 17, 40, 32, 73, 88, 75 
After Iter 3: 12, 16, 17, 40, 32, 73, 88, 75 
After Iter 4: 12, 16, 17, 32, 40, 73, 88, 75 
After Iter 5: 12, 16, 17, 32, 40, 73, 75, 88

Name the pivot selection strategy used in this QuickSort execution.

Hint: Examine what value is being selected as the pivot at each stage. Remember that QuickSort first sorts the left sub-array and its left-sub-array recursively before sorting the right sub-arrays.

It is using the most cost-effective solution of choosing the middle value. This is easy to select and has good efficiency when the data is already sorted (or mostly sorted) — paddy

fkl fkl · Accepted Answer · 2012-10-31T07:09:39

Any element is chosen as pivot and then in first iteration, all elements smaller than pivot are placed to the left of pivot and greater to the right, if they are already not. This means swapping pivot ahead in the array as well if needed. Knowing this and looking at the iteration should help identify the pivot.

For e.g. in your above case, i believe the middle element is being chosen as pivot i.e. 73. After first iteration, all elements lesser than it are moved to left and greater than it are moved to it's right.

Quicksort - Trouble identifying pivot

1 Answers