A pivot is an array element chosen by quicksort to divide a sequence into two subarrays. After partitioning, it occupies its final sorted position. section 15.6
Partitioning around a pivot proceeds as follows:
- Choose an element, commonly near the middle, and move it temporarily to the rightmost position. section 15.6.2
- Scan inward with indexes i and j, skipping values already correctly placed on the left or right. section 15.6.2
- Swap misplaced values while i remains left of j; stop when the indexes cross. section 15.6.2
- Swap the pivot into position, leaving values less than or equal to it on the left and greater values on the right. section 15.6.2
Pivot 52
Choosing 52 as the pivot rearranges the array so values less than or equal to 52 lie to its left and greater values lie to its right. Quicksort then processes both regions recursively. section 15.6.2
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.
Trace pivot choices, active subarrays, completed positions, and recursive partitioning across a full quicksort run. section 15.6.1
