Quicksort sorts an array by choosing a pivot, partitioning values around it, and recursively sorting the two resulting subarrays. The pivot reaches its final position after partitioning. section 15.6
Apply the algorithm in three stages:
- Stop for a subarray of zero or one element; swap if it contains exactly two elements and they are reversed. section 15.6
- Choose a pivot, move it temporarily to the right, and scan inward with indexes i and j. section 15.6.2
- Swap values that are on the wrong side, stop when the indexes cross, restore the pivot, and recurse on both sides. section 15.6.2
Quicksort in action
For an array beginning 86, 95, 51, 95, 28, 33, 9, 15, 84, 86, 67, choosing 33 as pivot moves smaller values left and larger values right before recursive sorting. section 15.6.1
Figure 15.11 The quicksort algorithm in action as it sorts an array. The circled values are the chosen pivot elements that create the subarrays on both sides after partitioning. The rectangles enclose the subarrays to be quicksorted recursively. In each line, the shaded subarray is the one actively being sorted. The values in bold are already in their correct places in the final sorted array. Note that the chosen pivot elements are always already in their correct places after partitioning.
Follow the pivot, boxed recursive subarrays, shaded active region, and bold values already in final positions. section 15.6.1
