Quickselect
Quickselect finds the element that would sit at position k if the array were sorted, such as the median, without paying the full cost of sorting. It is a cousin of quicksort that recurses into only one side.
How partitioning helps
Pick a pivot and rearrange the array so smaller elements come before it and larger ones after. After this partition the pivot lands in its final sorted position:
- If that position equals k, you are done.
- If k is smaller, recurse only into the left part.
- If k is larger, recurse only into the right part.
Because you discard one side each time, the average work is linear, much faster than the cost of a full sort.
Worst case and fixes
A poor pivot can degrade performance to quadratic. Choosing a random pivot makes bad cases unlikely, and the median of medians pivot guarantees linear time in the worst case.
Key idea
Partition like quicksort but recurse into only the side that can contain the kth element.