Selection and Order Statistics in O(n)
What This Concept Is
Selection returns one order statistic without fully sorting. This module's lab uses a zero-based index k: minimum is 0, maximum n-1, and an odd-sized median is n//2. Reject empty input and invalid k. Some books use one-based ranks; translate explicitly. With a three-way partition, descend only into the side containing k, or return immediately if k lies in the equal-key region.
Uniform random pivots give expected O(n) work, but the worst case is O(n²). The lab copies input once and partitions iteratively, using O(n) auxiliary slots. An in-place variant can avoid that copy if mutation is allowed.
Why It Matters Here
This exposes an output-contract tradeoff: one threshold, an unsorted top-K set, a sorted top-K list, and many rank queries need different amounts of information. A heap uses bounded streaming state; full sorting can amortize across repeated rank queries. Neither method universally wins in runtime.
Concrete Examples
In [9,1,1,4,7], select k=2. Pivot 1 creates below/equal/above regions of sizes
0,2,3; continue in the above region for the first value there. Pivot 4 then returns
4. Duplicate values occupy separate ranks, even when their numeric values match.
For an expected-time proof on distinct keys, call a pivot in the middle half good. It leaves at most about 3m/4 candidates. Conditional on any current set, a uniform pivot is good with probability at least one half, up to rounding. The expected number of attempts before a good pivot is bounded by a constant; every attempt before that shrink costs O(m). Group attempts into phases of sizes n, at most 3n/4, at most (3/4)²n, and so on. Expected total is the geometric sum O(n). This accounts for bad attempts; simply pretending every pivot is good does not prove the expectation.
Common Confusion / Misconceptions
Median-of-medians uses groups of five, recursively selects the median of their medians, then partitions. At least 3n/10-O(1) elements can be discarded, giving T(n) <= T(ceil(n/5)) + T(7n/10+O(1)) + O(n). An induction with a large enough linear constant proves O(n), after absorbing rounding into base cases. It does not compute the true median of the whole input as a cheap preliminary step. Library selection fallbacks vary; do not claim every implementation uses BFPRT or quote an unsupported constant-factor slowdown.
How To Use It
For one rank use a selection candidate; for streaming top-K consider O(K) heap state and O(n log(K+1)) work. Sorting the retained K adds O(K log K) if ordered output is required. For many rank queries on static data, include the upfront sort and subsequent O(1) indexed answers. Match the duplicate convention and input mutation policy before measuring.
Check Yourself
- Where are the bad-pivot attempts charged in the phase proof?
- Why do quicksort and quickselect pay for different recursion branches?
- Why is a fixed seed not a worst-case linear guarantee?
- How do rounding constants affect the BFPRT recurrence?
Mini Drill or Application
Implement the lab's iterative three-way selection. Compare every valid rank against sorting on exhaustive short arrays with duplicates. Show the all-equal case stops after one partition. Extension: implement groups-of-five pivot choice and prove the discard bound before comparing measured work. See P7.
Read This Only If Stuck
Use CLRS, Skiena, or Sedgewick and Wayne for randomized selection, phase analysis, and deterministic selection. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.