Selecting the Pivot

So far, we have selected the rightmost element as the pivot. Our analysis of quicksort was based on this presupposition. The analysis would be the same if we were to choose the leftmost element instead.

For the case of the sorted sequence, selecting the middle element would result in best-case performance. Generally, the ideal pivot is the median of the sequence to be partitioned.

Employing the median to sort may seem like the "chicken or the egg" problem since finding the median seems to require one to sort the sequence first! There are, however, celever algorithms to compute the median in linear time but those approaches are not considered practical choices.

Alternatively, one might calculate the average of all values or the mid-point value (as $\frac{max + min}{2}$). However, these strategies are $\Omicron(n)$ to compute and only good if the values in the sequence follow a normal (Gaussian) distribution.

Another strategy is to select a random element as the pivot and hope the choice makes for partitions of nearly equal length. It can be shown this strategy results in expected $\Omicron(n \lg n)$ worst-case runtime.

Exercise Trace the first pass of running quicksort (applying partitioning process) on the following sequence using the median of the three for your pivot choice.

$$ 20, \space 13, \space 7, \space 71, \space 31, \space 10, \space 5, \space 50, \space 17 $$

After selecting the pivot, swap it with the rightmost element, then apply partitioning. Use the following table to trace the process; show every swap in a different row.

Solution

Pivot is the median of $\{20, 31, 17\}$ which is $20$

Items in bold indicate the elements which were swapped.