Quicksort w/ "median of three" pivot selection: Understanding the process

Question

We're being introduced to Quicksort (with arrays) in our class. I've been running in to walls trying to wrap my head around how they want our Quicksort assignment to work with the "median of three" pivot selection method. I just need a high-level explanation of how it all works. Our text doesn't help and I'm having a hard time Googling to find a clear explanation.

This is what I think to understand so far:

The "median of three" function takes the elements in index 0(first), array_end_index(last), and (index 0 + array_end_index)/2(middle). The index with the median value of those 3 is calculated. The corresponding index is returned.

Function parameters below:

/* @param left
*       the left boundary for the subarray from which to find a pivot
* @param right
*       the right boundary for the subarray from which to find a pivot
* @return
*       the index of the pivot (middle index); -1 if provided with invalid input
*/
int QS::medianOfThree(int left, int right){}

Then, in the "partition" function, the number whose index matches with the one returned by the "median of three" function acts as the pivot. My assignment states that, in order to proceed with partitioning the array, the pivot must lie in-between the left and right boundaries. The problem is, our "median of three" function returned one of three indices: the first, the middle, or the last index. Only one of those three indices(middle) could ever be "in-between" anything.

Function parameters below:

/* @param left
*       the left boundary for the subarray to partition
* @param right
*       the right boundary for the subarray to partition
* @param pivotIndex
*       the index of the pivot in the subarray
* @return
*       the pivot's ending index after the partition completes; -1 if
*       provided with bad input
*/
int QS::partition(int left, int right, int pivotIndex){}

What am I misunderstanding?

Here are the entire descriptions of the functions:

/*
* sortAll()
*
* Sorts elements of the array.  After this function is called, every
* element in the array is less than or equal its successor.
*
* Does nothing if the array is empty.
*/
void QS::sortAll(){}

/*
* medianOfThree()
*
* The median of three pivot selection has two parts:
*
* 1) Calculates the middle index by averaging the given left and right indices:
*
* middle = (left + right)/2
*
* 2) Then bubble-sorts the values at the left, middle, and right indices.
*
* After this method is called, data[left] <= data[middle] <= data[right].
* The middle index will be returned.
*
* Returns -1 if the array is empty, if either of the given integers
* is out of bounds, or if the left index is not less than the right
* index.
*
* @param left
*       the left boundary for the subarray from which to find a pivot
* @param right
*       the right boundary for the subarray from which to find a pivot
* @return
*       the index of the pivot (middle index); -1 if provided with invalid input
*/
int QS::medianOfThree(int left, int right){}

/*
* Partitions a subarray around a pivot value selected according to
* median-of-three pivot selection.
*
* The values which are smaller than the pivot should be placed to the left
* of the pivot; the values which are larger than the pivot should be placed
* to the right of the pivot.
*
* Returns -1 if the array is null, if either of the given integers is out of
* bounds, or if the first integer is not less than the second integer, OR IF THE
* PIVOT IS NOT BETWEEN THE TWO BOUNDARIES.
*
* @param left
*       the left boundary for the subarray to partition
* @param right
*       the right boundary for the subarray to partition
* @param pivotIndex
*       the index of the pivot in the subarray
* @return
*       the pivot's ending index after the partition completes; -1 if
*       provided with bad input
*/
int QS::partition(int left, int right, int pivotIndex){}

Answer 1

Start with understanding quicksort first, median-of-three next.

To perform a quicksort you:

1. Pick an item from the array you are sorting (any item will do, but which is the best one to go for we'll come back to).
2. Reorder the array so that all items less than the one you picked are before it in the array, and all of those greater than it are after it.
3. Recursively do the above to the sets before and after the item you picked.

Step 2 is called the "partition operation". Consider if you had the following:

3 2 8 4 1 9 5 7 6

Now say you picked the first of those numbers as your pivot element (the one we picked at step 1). After we apply step 2 we end up with something like:

2 1 3 4 8 9 5 7 6

The value 3 is now in the correct place, and every element is on the correct side of it. If we now sort the left-hand side we end up with:

1 2 3 4 8 9 5 7 6.

Now, let's consider just the elements to the right of it:

4 8 9 5 7 6.

If we pick 4 to pivot next we end up changing nothing as it was in the correct position to begin with. To set of elements to the left of it is empty, so nothing to do here. We now need to sort the set:

8 9 5 7 6.

If we use 8 as our pivot we could end up with:

5 7 6 8 9.

The 9 now on its right is only one element, so obviously already sorted. The 5 7 6 is left to sort. If we pivot on the 5 we end up leaving it alone, and we just need to sort 7 6 into 6 7.

Now, considering all those changes in the wider context, what we have ended up with is:

1 2 3 4 5 6 7 8 9.

So to summarise again, quicksort picks one item, moves elements around it so that they are all correctly positioned relative to that one item, and then does the same thing recursively with the remaining two sets until there are no unsorted blocks left, and everything is sorted.

Let's come back to the matter I fudged over there when I said "any item will do". While it's true that any item will do, which item you do pick will affect the performance. If you are lucky you will end up doing this in a number of operations proportional to n log n where n is the number of elements. If you're just reasonably lucky it'll be a slightly bigger number still proportional to n log n. If you're really unlucky it'll be a number proportional to a number proportional to n².

So which is the best item to pick? The best number is the item that will end up in the middle after you have done the partition operation. But we don't know what item that is, because to find the middle item we have to sort all of the items, and that's what we were trying to do in the first place.

So, there are a few strategies we can take:

1. Just go for the first one, because, meh, why not?

2. Go for the middle one, because maybe the array is already sorted or nearly sorted for some reason, and if not it's not any worse a choice than any other.

3. Pick a random one.

4. Pick the first one, middle one and last one, and go for the median of those three, because it's at least going to be the best of those three options.

5. Pick the median-of-three for the first third of the array, the median-of-three of the second third, the median-of-three of the last third and then finally go with the median of those three medians.

These have different pros and cons, but generally speaking each of those options gives better results in picking the best pivot than the previous, but at the cost of spending more time and effort on picking that pivot. (Random has the further advantage of beating cases where someone is deliberately trying to create data that you will have worse-case behaviour on, as part of some sort of DoS attack).

My assignment states that, in order to proceed with partitioning the array, the pivot must lie in-between the left and right boundaries.

Yes. Consider above again when we had sorted 3 into the correct position, and sorted the left:

1 2 3 4 8 9 5 7 6.

Now, here we need to sort the range 4 8 9 5 7 6. The boundary is the line between the 3 and the 4 and the line between the 6 and the end of the array (Or another way of looking at it, the boundary is the 4 and the 6, but it's an inclusive boundary including those items). To three we pick is hence the 4 (first) the 6 (last) and either the 9 or the 5 depending on whether we round up or down in dividing the count by 2 (we probably round down as that's usual in integer division so the 9). All of these are inside the boundary of the partition we are currently sorting. Our median-of-three is hence 6 (or if we did round up, we'd have gone for the 5).

(Incidentally, a magically perfect pivot-chooser that always picked the best pivot just would have picked either the 6 or the 7, so picking 6 is pretty good here, though there are still times when median-of-three will be unlucky and end up picking the 3rd worse option, or perhaps even an arbitrary choice out of 3 equal elements all of which were the worse. It's just much less likely to happen than with other approaches).

Answer 2

The documentation for medianOfThree says:

* 2) Then bubble-sorts the values at the left, middle, and right indices.
*
* After this method is called, data[left] <= data[middle] <= data[right].
* The middle index will be returned.

So you description does not match the documentation. What you are doing is sorting the first, middle and last elements in-place in your data, and always returning the middle index.

So, it is guaranteed that the pivot index is in between the boundaries (unless when middle ends up bein in the boundary...).

Even so, there's nothing wrong with pivoting the boundaries...

Answer 3

Calculating the "median of three" is sort of a way to get a pseudo median element in your array, and having that index equal to your partition. Its a simple way to get a rough estimate of what the median of the array would be, leading to better performance.

Why would this be useful? Because in theory, you want to have this partition value to be the true median of your array, so when you do quicksort on this array, the pivot would have divided this array equally and enables the nice O(NlogN) sorting time that quick sort gives you.

Example: Your array is:

[5,3,1,7,9]

The median of three would look at 5, 1, and 9. The median is obviously 5, so this is the pivot value we want to consider for the partition function of quick sort. What you can do next is swap this index with the last and get

[9,3,1,7,5]

Now we attempt to have all values that are smaller than 5 on the left of the middle, all values bigger than five on the right of the middle. We now get

[1,3,7,9,5]

Swap the last element (where we stored the partition value) with the middle

[1,3,5,9,7]

And thats the idea of using the middle of 3. Imagine if our partition was 1 or 9. You could imagine that this array we would get would not be a good case for quick sort.