A subarray is a portion of an array treated as a separate sequence for an operation or recursive call. In quicksort, partitioning places a pivot between two subarrays, which are then sorted independently. section 15.6 section 15.6.2
Quicksort handles each subarray according to its size:
- A subarray of size zero or one needs no work. section 15.6
- A subarray of size two is sorted by swapping its elements when necessary. section 15.6
- Larger subarrays are partitioned around a pivot before recursive calls sort both sides. section 15.6.3
Partitioning around a pivot
For an array containing 86, 95, 51, 95, 28, 33, 9, 15, 84, 86, and 67, choosing 33 as the pivot rearranges values so smaller values lie to its left and larger values to its right. The resulting subarrays are ready for recursive sorting. 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.
Shows active and recursive subarrays, pivot positions, and values already in final positions during quicksort. section 15.6.1
