THE QUICKSELECT the kth smallest without sorting the rest — O(n) on average
To find the median, or the kth-smallest element, you do not need to sort the whole array. Quickselect (Hoare, 1961) partitions around a pivot like quicksort, but then recurses into only one side — the side that must contain the kth element — giving O(n) average time instead of O(n log n). Its key insight is that an element’s final position is its rank: the number of elements smaller than it. Find the element whose rank is k, and you are done, without ordering anything else. It is how you compute medians, percentiles, and top-k fast.
THE TECHNIQUE partition, recurse one side; rank(x) = #(elements < x) — O(n) avg
The demo finds the 3rd-smallest of [5,2,4,1,3] — the element whose rank is 2 (zero-based), which is 3: live demo
HISTORY & CREDIT Tony Hoare · 1961
“To find the median you must sort.” — quickselect finds it in O(n) average, ordering nothing else. cited
the rank · an element’s sorted position is rank(x) = #(y < x). the recursion · partition, then recurse into only the side holding rank k — O(n) average. 1961 · Tony Hoare — quickselect (with quicksort); medians, percentiles, top-k.
The kth element found by its rank, the rest left unsorted — selection without the full order. resource
RECOMMEND FOR I-13 the kth by rank, on the compiler
On the canonical compiler, the element of rank 2 (the 3rd smallest) in [5,2,4,1,3] is 3:
$ i13 run or_quickselect.i13 # find x with rank == k
RUN OK · 847 step(s) · peak stack 7 · call depth 11
third = 3 is3 = 1
Recommend as a NULL — resource, the do-less kind. Quickselect computes a value already determined by the array (the kth order statistic) using less work than a full sort (B40). Its answer is forall-pinned by the input (B39). No new invariant. NULL — the median without the sort.