Quicksort Pivot

Question

Sort the following array a using quicksort,

[6, 11, 4, 9, 8, 2, 5, 8, 13, 7]

The pivot should be chosen as the arithmetic mean of the first and the last element, i.e., (a[0] + a[size - 1]) / 2 (rounded down).

Show all important steps such as partitioning and the recursive calls to the algorithm.

---

I understand how to sort the array using quicksort, however I'm not sure how to calculate the pivot.

Is the pivot calculated by 6 + 7 = 13 then 13 / 2 = 6.5 (rounded down is 6) so the pivot is 2 (i.e. the 6th element)?

I know the elements less than pivot appear on the left hand side, and elements greater than the pivot appear on the right hand side, and the partition repeats this step of sorting the sub-array.

Any help would be greatly appreciated.

Cornwallis

Answer 1

For quicksort, the pivot can be whatever element you want. Check out Wikipedia.

The problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot

Three choices thus :

• First element
• Middle element
• Median of first, middle and last.

And in you case using the mean of first and last element value would give you :

6 + 7 = 13
13 / 2 = 6.5
6.5 rounded down = 6

Handmaid

I think this is wrong, but the error was in the original question. You corrected them, then did the bad calculation they asked for, when you took mean (first, last). You want the median of (first, middle, last). Although good point about how the instructor missed one of the better strategies for picking the pivot point (random). – Mute

Answer 2

For the given array [6, 11, 4, 9, 8, 2, 5, 8, 13, 7]

Calculate something like this:

• Select first element which is 6

• Select last element of list which is 7

• Select mid element which is mid = (length%2==0) ? (length/2)-1 : (length-1)/2, which is 8

• This makes an array and sort this it will be [6,7,8], now mid element in your array is the median.

Teriteria

Wow, that's an 8 year old question with no good answers til now. I gave you a vote, but your explanation is pretty sparse. – Mute

Answer 3

By the way the question is worded, the pivot should just be 6 and not necessarily the 6th item in the array.

This is most definitely the case because if there were only 3 items in the array, for example, and the arithmetic mean came out to be greater than 3, you would have no pivot to choose because there is no item with that index.

Note: Be careful with the way you index elements in your array. You said the 6th element is '2', when it may be '5' if your programming language starts indices at 0.

Febrile

Answer 4

Your pivot is 6. Your pivot is NOT the 6th element Now you can apply the following algorith.

function quicksort(array)
 var list less, greater
 if length(array) ≤ 1
     return array  // an array of zero or one elements is already sorted
 select and remove a pivot value pivot from array
 for each x in array
     if x ≤ pivot then append x to less
     else append x to greater
 return concatenate(quicksort(less), pivot, quicksort(greater))

Altruism

Answer 5

The position of the pivot from that calculation is not important, quicksort sorts the elements based on whether they are more or less than the pivot. Then the pivot is placed in between the two sets (more and less).

Expeditious

Is it possible for pivot element to not be in the array? – Homans