Selection without sorting
Sometimes you only need the kth smallest element, not the entire sorted order. Randomized quickselect finds it by borrowing the partition step from quicksort but recursing into only one side, so on average it runs in linear time.
The partition and the recursion
You pick a random pivot and partition the array so that smaller elements go left and larger ones go right. After partitioning, the pivot lands in its final sorted position.
- If the pivot's position equals the target rank, you are done.
- If the target rank is smaller, recurse only into the left part.
- If the target rank is larger, recurse only into the right part.
Because you discard one side every time, the expected work shrinks geometrically and sums to a linear total.
Why randomness matters
A fixed pivot choice can be defeated by an adversarial input that always splits off one element, degrading to quadratic behavior. Choosing the pivot at random makes such bad splits unlikely, so the linear expected time holds for any input.
Key idea
Partition around a random pivot and recurse into only the side holding the target rank, giving expected linear selection without sorting everything.