Finding the ith smallest element in linear time — expected, and then in the worst case, by a trick that picks a good pivot by recursion.
Sorting gives you every order statistic at once for Θ(n lg n). If you want only one — the minimum, the median, the 99th percentile — you should not have to pay for all of them. Chapter 9 shows you do not. Randomized selection reuses quicksort’s partition but recurses into only one side, giving expected Θ(n). Then the chapter does something more surprising: it achieves Θ(n) in the worst case, using the median-of-medians algorithm, which guarantees a good pivot by recursively finding one.
SELECT and is presented with groups of 5 as before; the 4th edition tightens the exposition of why the group size must be at least 5.ith order statistic of a set of n elements is the ith smallest. The minimum is the 1st, the maximum is the nth, and the median is the halfway point — the lower median at i = ⌊(n+1)/2⌋ and the upper median at i = ⌈(n+1)/2⌉. For odd n they coincide. CLRS says “the median” to mean the lower one.The selection problem: given a set A of n distinct numbers and an integer i with 1 ≤ i ≤ n, find the element of A that is larger than exactly i-1 other elements.
The obvious solution is to sort and index, for Θ(n lg n). The whole chapter is about doing better.
The minimum is easy and the analysis is a good warm-up.
MINIMUM(A, n)
1 min = A[1]
2 for i = 2 to n
3 if min > A[i]
4 min = A[i]
5 return minn-1 comparisons, and that is optimal: every element except the winner must lose at least one comparison to be eliminated, so n-1 losses are required.
Now suppose you want both the minimum and the maximum. The naive approach runs both loops for 2n - 2 comparisons. You can do better.
3⌊n/2⌋ comparisons total — a 25% saving.Initialise by comparing the first two elements if n is even, or setting both min and max to the single first element if n is odd.
For general i, the algorithm is quicksort with one recursive call deleted.
RANDOMIZED-SELECT(A, p, r, i)
1 if p == r
2 return A[p] // one element: it is the answer
3 q = RANDOMIZED-PARTITION(A, p, r)
4 k = q - p + 1 // rank of the pivot within A[p:r]
5 if i == k
6 return A[q] // the pivot IS the answer
7 elseif i < k
8 return RANDOMIZED-SELECT(A, p, q-1, i)
9 else
10 return RANDOMIZED-SELECT(A, q+1, r, i-k)Note line 10: when recursing right, the rank must be adjusted by k, because the k elements at or before the pivot are no longer in the subarray.
cn; selection’s shrink by a constant factor, and a decreasing geometric series sums to O(n).Worst case Θ(n²). If every partition peels off one element and we always recurse into the larger side, we get T(n) = T(n-1) + Θ(n) = Θ(n²). As with quicksort, randomization makes this vanishingly unlikely rather than impossible.
Expected Θ(n). The intuition is the geometric series in Figure 9.1. Suppose each partition is at worst a 9-to-1 split and we always land on the bigger side:
T(n) ≤ T(9n/10) + cn
≤ cn + (9/10)cn + (9/10)²cn + …
= cn · 1/(1 - 9/10) = 10cn = O(n)cn all the way down and it picks up the lg n factor from the depth. Selection discards one side, so its per-level cost decays geometrically, and a decaying geometric series is dominated by its first term. The lg n disappears because half the work is thrown away.CLRS makes this rigorous by conditioning on the pivot’s rank. Each rank k is equally likely, and the recursion always continues into the larger side in the worst case, giving
E[T(n)] ≤ (2/n) · ∑ from k=⌊n/2⌋ to n-1 of E[T(k)] + O(n)Substitution with the guess E[T(n)] ≤ cn closes it out. Expected running time is Θ(n) for any i, including the median.
Randomization gives an expected bound. Can we get a guarantee? Yes, and the technique is one of the most ingenious in the book.
The problem with quicksort-style partitioning is that a bad pivot ruins it. So compute a provably good pivot — and do it recursively, using the very algorithm being defined.
SELECT(A, p, r, i) // worst-case linear time
1 Divide the n elements into ⌊n/5⌋ groups of 5,
plus one leftover group of n mod 5 elements.
2 Find the median of each group by insertion-sorting its
≤ 5 elements and taking the middle one. Θ(1) per group.
3 Recursively SELECT the median x of the ⌈n/5⌉ group medians.
4 PARTITION the array around x. Let k be x's rank.
5 if i == k return x
elseif i < k recurse on the low side
else recurse on the high side for i-kStep 3 is the twist: the algorithm calls itself to find its own pivot. Two recursive calls of different sizes, on different arrays.
≤ x, and each of those groups contributes 3 elements ≤ x — its median and the two below it.The guarantee. At least half of the ⌈n/5⌉ group medians are ≥ x. Each such group contributes at least 3 elements ≥ x (its median and the two above it), except possibly x’s own group and the short leftover group. So the number of elements ≥ x is at least
3·( ⌈½·⌈n/5⌉⌉ - 2 ) ≥ 3n/10 - 6Symmetrically for elements ≤ x. Therefore neither side of the partition exceeds 7n/10 + 6 elements — a constant-fraction split, guaranteed, on every input.
The recurrence:
T(n) ≤ T(⌈n/5⌉) + T(7n/10 + 6) + O(n)
↑ ↑ ↑
find the pivot recurse on one side group + partitionSubstitution with the guess T(n) ≤ cn works because 1/5 + 7/10 = 9/10 < 1. The two subproblems together are strictly smaller than the original, so the extra work is absorbed and T(n) = O(n).
1/5 + 7/10 < 1 is the entire algorithm in one inequality. Unlike a normal divide-and-conquer where subproblem sizes sum to n and you pay a lg n factor for the depth, here they sum to strictly less than n, so the work decays geometrically and the total stays linear.The choice of 5 is not arbitrary, and checking the alternatives is the fastest way to see what the algorithm is actually doing.
| Group size | Pivot subproblem | Partition subproblem | Sum | Works? |
|---|---|---|---|---|
| 3 | n/3 | ≈ 2n/3 | 1/3 + 2/3 = 1 | No — gives Θ(n lg n) |
| 5 | n/5 | ≈ 7n/10 | 1/5 + 7/10 = 9/10 | Yes |
| 7 | n/7 | ≈ 5n/7 | 1/7 + 5/7 = 6/7 | Yes, but bigger constant |
Groups of 3 fail because the two subproblem fractions sum to exactly 1, which is precisely the balanced case that yields Θ(n lg n). Five is the smallest odd group size that pushes the sum below 1. Larger odd sizes also work but make step 2 more expensive without improving the asymptotics.
O(1) per group only because the group size is a constant — sorting 5 elements takes at most 7 comparisons no matter how large n is.RANDOMIZED-SELECT is dramatically faster in practice despite the weaker guarantee. The standard engineering answer is the same hybrid pattern as introsort — introselect: run RANDOMIZED-SELECT, and if it fails to make progress after a few rounds, fall back to SELECT for a hard O(n) guarantee. That is what std::nth_element does.| Task | Approach | Cost |
|---|---|---|
| Minimum or maximum | Single scan | n-1 comparisons, optimal |
| Both min and max | Process in pairs | 3⌊n/2⌋ comparisons |
| One order statistic | RANDOMIZED-SELECT | Θ(n) expected |
| One order statistic, guaranteed | SELECT (median of medians) | Θ(n) worst case |
The k smallest, k small | Max-heap of size k | O(n lg k) |
| Many order statistics | Just sort | Θ(n lg n) once |
The last row matters. Selection beats sorting for one query. If you need several, sorting once and indexing is cheaper than repeated selection.
ith order statistic is the ith smallest. Selection finds one without sorting all of them.n-1 comparisons and that is optimal. Min and max together take only 3⌊n/2⌋, by comparing elements in pairs first.RANDOMIZED-SELECT is quicksort with one recursive call removed. Expected Θ(n), worst case Θ(n²).lg n factor disappears because one side is discarded: level costs decay geometrically instead of staying flat.7n/10 + 6, giving T(n) ≤ T(n/5) + T(7n/10) + O(n), which is linear because 1/5 + 7/10 < 1.Θ(n lg n)); 5 is the smallest size that works. In practice use randomized selection, with SELECT only as a fallback.Part II is complete. Part III turns from algorithms to the structures they run on. Chapter 10 covers the elementary ones — arrays, linked lists, stacks, queues, and rooted trees — and it is the foundation that hash tables, binary search trees, and red-black trees are all built on. These next four chapters are the ones most worth knowing cold, so this recap gives them extra room.