[k] QuickSelect

Imagine a race with a hundred runners and someone asks, "who finished 3rd?" You don't need the full finishing order to answer that — you just need the third name. QuickSelect does exactly this for a list of numbers: it finds the $k$-th smallest value without bothering to sort the whole list.

The trick is partitioning. Pick one number as the pivot, then sweep through the list and push everything smaller to its left and everything larger to its right. Now the pivot sits in its final sorted spot, and you can read off its rank — how many values are at or before it. Take the list $[7, 2, 9, 4, 1]$ and look for the 2nd-smallest ($k=2$). Pick pivot $4$: the smaller pile is $\{2,1\}$ and the larger pile is $\{7,9\}$, so $4$ lands 3rd and its rank is $3$. Since $k=2$ is less than $3$, the answer must be hiding in the left pile, so we repeat the trick there and throw the rest of the list away.

Throwing half away is the whole point. Quicksort recurses into both halves and costs $O(n \log n)$; QuickSelect chases only the one half that can contain the answer. On a balanced split the work shrinks geometrically, $n + n/2 + n/4 + \dots = 2n$, so the average cost is just $O(n)$ — linear, faster than sorting.

The precise version. If a pivot settles at index $p$ within the range starting at $\text{lo}$, its rank is $\text{rank} = p - \text{lo} + 1$. The average-case recurrence $T(n) = T(n/2) + O(n)$ sums to $O(n)$. The catch is the worst case: if the pivot is always the smallest or largest value the split is useless and $T(n) = T(n-1) + O(n) = O(n^2)$. Choosing the pivot at random makes that essentially impossible, and the median-of-medians (BFPRT) rule guarantees $O(n)$ even in the worst case.

Try this with the controls above. (1) Trace the pseudo-code panel by hand on $[7,2,9,4,1]$ for $k=2$, following the three branches at rank == k, k < rank, and k > rank. (2) Switch the preset to Sorted, then Reverse — these are exactly the inputs that wreck a naive "always pick the first element" pivot and drag QuickSelect toward its $O(n^2)$ worst case, which is why real implementations randomise. (3) Type a custom list with repeats like 5,5,5,5,5 to picture the equal-keys case that three-way partitioning is built to handle.

Step 1 -- Relation to Quicksort. QuickSelect reuses Quicksort PARTITION. Pivot lands at final sorted position p. Unlike Quicksort which recurses both halves, QuickSelect recurses into only ONE half based on k vs rank.

Step 2 -- Average Case. Expected balanced partition: T(n) = T(n/2) + n. Geometric series: n + n/2 + n/4 + ... = 2n. T(n) = O(n) average -- much better than sorting O(n log n).

Step 3 -- Worst Case. Pivot always min or max: T(n) = T(n-1)+n => O(n^2). Randomized pivot gives O(n) expected. BFPRT (Median-of-Medians) guarantees O(n) worst case.

Step 4 -- Median-of-Medians (BFPRT). Divide into groups of 5, find each median (6 comparisons), recursively select median of medians, use as pivot. Guarantees pivot between 30th-70th percentile. T(n)=T(n/5)+T(7n/10)+O(n) => O(n).

Step 5 -- Why groups of 5? Groups of 3: recurrence does not converge to O(n). Groups of 5: smallest odd size giving O(n) convergence with manageable constant. Median of 5 found in exactly 6 comparisons.

Step 6 -- std::nth_element. C++ std::nth_element uses introselect -- QuickSelect with Median-of-Medians fallback guaranteeing O(n) worst case. Returns k-th element with partial sort.