Algorithms in a Nutshell

Quicksort

If we reflect on the performance of Median Sort, we see that a random choice of pivotIndex still enables the average-case performance of selectKth to operate in linear time. Is it possible to simplify the algorithm without incurring an extra performance penalty? Would the simpler implementation perhaps be faster in some situations? The Quicksort algorithm, first introduced by C.A.R. Hoare, is indeed simpler than Median Sort, although it uses many of the same concepts, which is why we introduced Median Sort first.

In Quicksort, we no longer seek the median value, and instead select an element according to some strategy (sometimes randomly, sometimes the leftmost, sometimes the middle one) to partition an array into subarrays. Thus Quicksort has two steps, as shown in Figure 4-11. The array is partitioned around a pivot value, creating a left subarray that contains elements less than or equal to the pivot, and a right subarray that contains elements greater than or equal to the pivot. Each of these subarrays is then recursively sorted.

Figure 4-11. Quicksort fact sheet

The random nature of the algorithm as described makes it a challenge to prove that the average-case performance is still O(n log n). We do not cover here the advanced mathematical analytic tools needed to prove this result, but further details on this topic are available in (Cormen et al., 2001).

Figure 4-12 shows ...