randomized selection
Sometimes you do not need the whole list sorted — you just want the k-th smallest item, for example the median. Sorting everything to read off one position is wasteful. Randomized selection finds the k-th smallest directly, using the same random-pivot idea as quicksort but recursing into only one side, which makes it run in linear time on average instead of n log n.
Precisely: pick a pivot uniformly at random and partition the array; suppose the pivot lands in position p. If p equals k you are done; if k < p the answer lies in the left part, and if k > p it lies in the right part — so you recurse into just that one side, discarding the rest. Because each partition throws away a constant fraction of the elements on average, the expected total work is a geometric series, n + (3/4)n + (9/16)n + ... = O(n), linear time. A clean way to see the constant fraction: a random pivot lands in the middle half of the order (between the 25th and 75th percentile) with probability one-half, and such a pivot discards at least a quarter of the elements; on average you need only a couple of partitions to shrink the problem by a constant factor.
Randomized selection matters because it is the simplest way to get expected linear-time selection, and it is the heart of fast median-finding used inside other algorithms. It is the random cousin of the deterministic median-of-medians method, which guarantees O(n) worst case but with larger constants and more code. The honest caveat: like randomized quicksort, the worst case is O(n^2) if pivots are repeatedly unlucky, and the O(n) is an expectation over the coin flips. In practice it is fast and simple; when you need a hard worst-case guarantee, use median-of-medians instead.
To find the 3rd smallest of [7, 2, 9, 4, 1, 6]: a random pivot 4 partitions into [2,1] (smaller) | 4 | [7,9,6] (larger), so 4 sits in position 3 — exactly the answer, no recursion needed. Had we wanted the 5th smallest, we would recurse only into the right part [7,9,6].
Recurse into one side only: expected O(n), but worst case O(n^2).
Selection beats sorting only because it recurses into one side, not both — that single change turns n log n into expected n. But the guarantee is expected linear, not worst-case linear; for a hard O(n) bound use median-of-medians.