Intuition The one idea behind this whole topicWe want just one item from a pile of numbers — the item that would sit at a chosen rank if we bothered to sort everything — but we refuse to pay the full sorting price. The entire topic is a hunt for a pivot (a splitting value) that is guaranteed not to be near the extremes, because a middle-ish pivot lets us throw away a fixed slice of the pile every step and finish in time proportional to the pile's size.
Before you can read the parent note, you must own every symbol it fires at you. We build them one at a time, each anchored to a picture, each earned before use.
Definition Array and its lengthAn array A A = [ 12 , 3 , 5 , … ] length , written n
Picture a shelf of numbered boxes. The order they sit in is whatever we were handed — not sorted. That "unsorted" fact is the whole reason the topic exists.
Why the topic needs it: every cost in the parent (like O ( n ) n n
Definition Rank and the targetk did sort the numbers small-to-large, each would get a position from 1 n k 1 ≤ k ≤ n which position we want . The answer is the number that would land at position k
k k = 1 k = n k who ends up at seat k .
Why the tool and not another? We could sort to read off seat k all n one . That over-answering is exactly the waste we want to avoid. This is the Order statistics view: the "k k
Common mistake Off-by-one: isk Why it trips people: most code arrays start at index 0 The fix: the parent uses 1-indexed ranks (k = 1 sorted(A)[k-1] in code, but always speak of k
Definition Big-O — a growth rate, not a stopwatchO ( ⋅ ) how the work grows as the pile grows , ignoring constant multipliers and small terms. O ( n ) n O ( n 2 ) square (double the pile, four times the work). O ( n log n )
Intuition The picture: curves pulling apartDraw three curves against n O ( n ) O ( n log n ) O ( n 2 )
Why the topic needs it: the whole point is "O ( n ) worst-case ." Without a feel for these curves, that claim is empty. See Recurrence relations and the Master Theorem for how such costs are computed.
O ( n ) O ( n 2 ) Why it feels right: the curves say so for big n The fix: Big-O hides constants. An O ( n ) lose to an O ( n log n ) growth , not raw speed at a given size.
A pivot p dividing line : everything smaller goes left, everything larger goes right.
To partition around p smaller than p , equal to p , larger than p — walking through the array once. After partitioning, p true sorted index even though the rest is still messy.
Definition The pivot's landing indexi p would have in the fully sorted array. Call that seat number i 1 k L p p == i = L + 1 == L i fact we read off for free from the single partition sweep.
WHY partition at all? Once we know the pivot's landing index i k
i = k is the answer, stop.k < i k > i
We just deleted a whole side of the array with one pass. This is the engine of Quickselect and the sibling algorithm Quicksort . The mechanics of the single sweep are the topic of Partitioning (Lomuto vs Hoare) .
Intuition Why the pivot'squality is everything
If p i ≈ n /2 ≈ n /2 p i = 1 i = n single box. Same O ( n ) O ( n ) O ( n 2 ) Choosing a pivot that can't be terrible is the entire battle the parent fights.
The median of a list is its middle value once sorted . For an odd count like 5, it's the 3rd of 5 — two below, two above.
Definition Group median → median of mediansChop the pile into groups of 5 . Take each group's median (cheap — 5 items is constant work). Collect those medians into a smaller pile and find that pile's median. This final value M median of medians , and it becomes our pivot.
WHY this dance? A single "middle-of-a-group" median could still be extreme for the whole array. But the median of the medians is a middle value of middle values — it is surrounded on both sides by a guaranteed slice of the pile, so it can never be a near-extreme pivot.
10 3 n 5 n columns , and inside each column sort the 5 boxes top-to-bottom. Now slide the columns so their middle boxes (the group medians) line up in a row, ordered by value — small-median columns on the left, large-median columns on the right (see the figure).
By definition of M half the group medians are ≤ M ≈ 2 1 ⋅ 5 n = 10 n
In each of those left columns, the median and the two boxes above it (3 of the 5) are ≤ ≤ M
So the shaded rectangle of guaranteed-small boxes is 3 × 10 n = 10 3 n ≤ M
By the mirror-image argument, ≥ 10 3 n ≥ M other side can hold at most n − 10 3 n === 10 7 n == 10 7 n Randomized algorithms , which get a good pivot only on average , with no such rectangle guarantee.)
Definition Ceiling and floor⌈ x ⌉ up to the nearest whole number: ⌈ 2.2 ⌉ = 3 ⌊ x ⌋ down : ⌊ 2.9 ⌋ = 2 n
T ( n ) T ( n ) worst-case total work (count of comparisons and element-moves, up to a constant) the whole Select algorithm does on any input of size n n T T
Definition The base case — small piles stop the recursionRecursion must bottom out or it never ends. When ==n ≤ 5 not recurse: we simply sort those few boxes directly and read off seat k − 1 constant time. So T ( n ) = O ( 1 ) n ≤ 5
≤ = " W ec a n ′ t k n o w t h e ∗ e x a c t ∗ s pl i t , b u tw e ∗ ∗ c an ∗ ∗ p r o mi se i t ′ s n o w or se t han t h ese f r a c t i o n s . W or s t − c a se b o u n d s l i v e in t h e l an g u a g eo f " Recurrence relations for how such an inequality is solved.
Intuition The punchline symbol:5 1 + 10 7 < 1 5 1 + 10 7 = 10 9 less than 1 , the sub-piles together are strictly smaller than the pile you started with — so the work drains to zero fast enough to sum to O ( n ) 1 3 1 + 3 2
Pivot p and landing index i
3n/10 guarantee -> 7n/10 side
Test yourself — each should feel obvious before you open the parent note.
What does n A n A A not sorted.
What does the target k The rank we want; the answer is the value at seat k A k = 1
In one sentence, what does O ( n ) O ( n 2 ) How the work grows with pile size — linearly versus quadratically; it ignores constant factors.
What is a pivot, and what does partitioning produce? A chosen dividing value; partitioning rearranges into smaller / equal / larger zones and fixes the pivot's final sorted index.
What is the pivot's landing index i The rank the pivot occupies after partitioning; if L p i = L + 1
Why does a min/max pivot cause O ( n 2 ) It sheds only one element per step (i = 1 i = n n
What is the median of a 5-element group? The 3rd value after sorting the 5 (two below, two above).
What is M The median of all the group medians; a rectangle of 3 n /10
Where does the 7 n /10 At least 3 n /10 M n − 3 n /10 = 7 n /10
What does T ( n ) Worst-case total work of Select on size-n n ≤ 5 T ( n ) = O ( 1 )
What do ⌈ x ⌉ ⌊ x ⌋ Round up and round down to the nearest integer, respectively.
Why is 5 1 + 10 7 < 1 Because the two recursive sub-piles together shrink the problem by a constant factor < 1 O ( n )
