Selecting without sorting
To find the kth smallest element you do not need a full sort. Quickselect borrows quicksort's partition step but recurses into only one side, the side that must contain the answer.
The procedure
- Choose a pivot and partition the array so smaller values land left and larger values land right.
- After partitioning the pivot sits in its final sorted position.
- Compare that position to k: if it equals k you are done; if k is smaller recurse left, otherwise recurse right.
- Each step discards one whole side, so on average the work shrinks geometrically.
Cost and risk
- On average the discarded portions sum to a small multiple of the array size, giving linear average time.
- A consistently bad pivot, like always the largest, can degrade to scanning the array once per element.
- Choosing pivots randomly, or using the median of medians rule, tames the worst case.
Why it matters
- Computing a percentile, the top k, or a median uses selection, not a full ordering.
- It is the engine behind several order statistic routines in standard libraries.
Key idea
Quickselect partitions like quicksort but recurses into only one side, finding the kth element in linear average time without a full sort.