A pivot is the selected list element whose value divides the elements being processed into lower and higher partition regions. After partitioning, the pivot occupies its final sorted position. section 15.6 section 15.6.2
A partition uses the pivot as follows:
- Choose an element, commonly near the middle, and move it temporarily to the right. section 15.6.2
- Scan from both sides, exchanging values so elements less than or equal to the pivot move left and greater values move right. section 15.6.2
- Return the pivot index, then recursively quicksort the sublists on either side. section 15.6.3
Partitioning around 52
Selecting 52 and partitioning places every value less than or equal to 52 on its left and every greater value on its right; both sublists remain to be sorted. section 15.6.2
Figure 15.12 Choosing 52 (circled) to be the pivot value and then partitioning the list into two sublists. Variables i and j are list indexes. After partitioning, all values to the left of 52 are less than or equal to it, and all values to the right of 52 are greater. The two boxed sublists on either side of the pivot are now ready to be recursively quicksorted.
Use the figure to trace pivot selection, index movement, exchanges, and the resulting recursive sublists. section 15.6.2
