Partition is the whole of quicksort that is not recursion. One pass over n elements, n − 1 comparisons against the pivot, and three regions whose boundaries are the loop's two indices: at most the pivot, above the pivot, not yet examined. At the end one element is where it belongs for ever, and nothing else has been sorted.
Core ideas
The hard idea is the invariant: a statement true before the loop, preserved by one step of it, and strong enough at the end to be the postcondition.
Lomuto's loop keeps a[lo..i] at most the pivot, a[i+1..j−1] above it, and a[j..hi−1] unexamined. Before the first step i = lo − 1 and j = lo, so the first two regions are empty and the invariant holds of any array at all. Each step examines a[j]: if it is above the pivot, j advances and the middle region grows; if not, i advances and a[i] is swapped with a[j], moving one element out of the middle region and one into the first.
Every element except the pivot is compared with the pivot exactly once, so a Lomuto partition of twelve elements costs eleven comparisons whatever the twelve are. That is the only figure on the lab's panel that does not depend on the data, and it is what makes quicksort's cost the sum of its subarray sizes rather than something that has to be measured. Hoare's two-pointer scheme stops when the pointers cross, so its count does depend on the data: on the lab's default array it makes fourteen comparisons where Lomuto makes eleven.
After the final swap the pivot sits at index i + 1 with everything at most it to the left and everything above it to the right, so it is at its final sorted position and will never be touched again. Neither side is sorted. On the lab's default array the left side comes out 3 9 10 16 7 and the right side 43 55 38 27 91 82, and reading either as sorted is the mistake this lesson exists to prevent.
The material
The loop, the three regions, the proof that the pivot is placed, and what Hoare does differently.
To partition a[lo..hi] around a pivot value p drawn from it is to rearrange the subarray so that p sits at some index q with a[lo..q−1] ≤ p and a[q+1..hi] > p. The index q is returned; it is not chosen in advance and is not generally the middle.
Lomuto's scheme is the one this course counts. Swap the chosen pivot to the end of the subarray, walk j from lo to hi − 1, and keep a second index i marking the end of the at-most-pivot region. That is the whole algorithm, and the pseudocode of it is four lines in the block above.
A loop invariant is a statement about the program's state that is true before the loop begins, and true after each iteration if it was true before that iteration. It is useful when its truth at the loop's exit, together with the exit condition, gives the postcondition you wanted.
The invariant here is the three regions. It holds before the loop because two of the regions are empty. It is preserved by each step, in the two cases the concept card gives. And at exit j = hi, so the unexamined region is empty and the array is exactly at most | above | pivot, one swap away from what was wanted.
When the loop exits, swapping a[i+1] with a[hi] leaves the pivot at index i + 1 with every element of a[lo..i] at most it and every element of a[i+2..hi] above it. The pivot is therefore at its final position in the sorted array.
At exit the invariant gives a[lo..i] ≤ p and a[i+1..hi−1] > p, with the pivot itself still at hi.
The final swap exchanges the pivot with a[i+1], which is above the pivot, so it lands in the region of elements above the pivot, where it belongs. The pivot lands at i + 1. Every element to its left is at most it and every element to its right is above it, which is the definition of that position being its place in sorted order — and that is a property of the final array, not of this pass, so no later recursion can disturb it.
□
The array is 38 27 43 3 9 82 10 55 16 7 91 24 and the pivot is the last element, 24. Eleven comparisons and six swaps later the array is 3 9 10 16 7 24 43 55 38 27 91 82, with the pivot at position six. Five elements are at most 24 and six are above it, and neither group is in order. The worked example below steps through all eleven comparisons.
Hoare's partition walks one index up from the left and one down from the right, swapping an out-of-place pair whenever both stop, and finishes when the indices cross. It does about a third as many swaps as Lomuto on typical data — four rather than six on the lab's array — and it does not place the pivot at a known index; it returns a boundary. Its comparison count is data-dependent, which is why the clean n − 1 above is stated for Lomuto and not for partition in general.
Both schemes send keys equal to the pivot to one side. That sounds like a detail and it is the subject of a counterexample two lessons from here: on an array whose keys are all equal, Lomuto splits n into 0 and n − 1 under every pivot rule there is, including a randomised one.
Two things are worth checking in the lab's step table. The i and j columns count from zero, which is why i starts at −1: the at-most region is empty, and an index one before the start is how that is said. And the invariant column is evaluated on the array at that step rather than assumed, so a broken invariant would appear as the word BROKEN and not as a missing row.
Interactive
Three regions, a pointer each, and the invariant evaluated after every comparison
Method
Write the two indices down at every step. The array alone does not tell you where the regions are.
Swap the chosen pivot to the last position of the subarray. Set j to the first position and i to one before it. Say out loud what the invariant asserts now: both named regions are empty, so it holds.
If a[j] is above the pivot, do nothing but advance j; the middle region grew. If a[j] is at most the pivot, advance i, swap a[i] with a[j], then advance j. Exactly one comparison happens per step, which is where n − 1 comes from.
After each step, read the array back: everything up to i should be at most the pivot and everything from i + 1 to j − 1 above it. This is the step where an off-by-one in the swap shows up, while it is still one line of work to undo.
Swap a[i+1] with the pivot at the end. Now say the postcondition: one element is final, the two sides are separated, and neither side is sorted. If you catch yourself expecting a sorted side, look at the lab's final row.
Lomuto makes n − 1 comparisons on every array. The panel prints that beside ⌈log₂ n!⌉, the number any comparison sort needs for the whole job, so the two figures on screen are one measurement and one proof about every algorithm. Sorting twelve elements needs at least twenty-nine comparisons; one partition of them spends eleven.
The array is the lab's default and the pivot is its last element, 24. The indices are written as the lab writes them, counting from zero, so i = −1 means the at-most region is still empty. The array shown on each line is the array after that step.
Five steps moved something and six did not, and the six that did not are where the middle region grew. The pivot's final position, six, was not chosen: it is one more than the number of elements at most 24, which the pass discovered.
Now read the two sides. 3 9 10 16 7 is not sorted and neither is 43 55 38 27 91 82. Everything the pass promised is true and nothing more is: one element final, two groups separated, n − 1 comparisons spent.
For a faded rehearsal, change the pivot position slider to 1, so the pivot is 38. The supplied first move is the count: it is still eleven comparisons, because Lomuto's count does not depend on which element is the pivot. Predict the pivot's final position before running it — count how many of the twelve keys are at most 38 — and then check the swap count, which does change.
You should be able to partition twelve elements around a named pivot, say why the comparison count is n − 1 before running it, predict the pivot's final position by counting, and state the postcondition without claiming either side is sorted.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.