Quicksort's partition
Pick the last element as pivot. Rearrange so everything ≤ pivot is on its left and everything bigger is on its right. Then the pivot is in its final place.
The textbook partition
Three regions, left to right, plus the pivot.
| Slice | Meaning |
|---|---|
| A[p..r] | the sub-list to partition |
| A[r] | the pivot \(x\) |
| A[p..i] | values ≤ pivot |
| A[i+1..j-1] | values > pivot |
| A[j..r-1] | not investigated yet |
Start with \(i=p-1\) and \(j=p\): the first two regions are empty, so everything is uninvestigated. The index \(j\) scans left to right, and each iteration is one of two cases:
- A[j] > x: only j++. The value joins the >x block for free.
- A[j] ≤ x: i++, exchange A[i] with A[j], then j++. The swap pushes the first big value out to position \(j\) and brings a small one forward.
After the loop, exchange A[i+1] with A[r] and return i+1. Every value left of that index is ≤ pivot, every value right of it is > pivot.
Why it is correct: the loop invariant
At the top of each iteration the regions above hold. Initialization: the ≤x and >x blocks are empty. Maintenance: the two cases above each keep all three regions valid and move one value out of "uninvestigated". Termination: when \(j=r\), nothing is uninvestigated, so the array is just ≤x, >x, pivot, and the last swap puts the pivot between them.
Cost
The loop runs \(r-p\) times and does constant work each time, so partitioning \(n\) elements is \(\Theta(n)\). That \(\Theta(n)\) is the \(f(n)\) in quicksort's recurrence. A balanced split gives \(T(n)=2T(n/2)+\Theta(n)\), which you can unroll on the Recurrences page. A fully unbalanced split gives \(T(n)=T(n-1)+\Theta(n)=\Theta(n^2)\).
Things to try in the stepper
- Textbook example: watch the swaps happen only when a value is ≤ the pivot.
- Sorted input: every value is ≤ the pivot, so there is a swap (with itself) every time and the split is as unbalanced as possible.
- All >pivot: \(i\) never moves and there are no swaps until the last step.
- Ties: equal values go to the ≤ side.
A good exercise
The textbook version grows both blocks from the left. Try sketching the same algorithm with the >x block growing in from the right instead, with the uninvestigated values in the middle. Which index decides which case? Where does the loop stop? Which invariant slice changes? Work out the picture and the code yourself, then use the stepper above to sanity-check your ideas on the textbook version.