A selection algorithm that uses array partitioning around a pivot and recursively searches only the side containing the desired order statistic. If there are entries before the placed pivot, an earlier rank is unchanged and a later rank is reduced by . Segment length strictly decreases, proving algorithm termination. The same reduction can update local bounds in a loop, using constant auxiliary space.
Balanced reductions give linear work by a geometric series, while repeatedly discarding only a constant number of entries can give quadratic work. For distinct entries and independent uniform random pivots, a pivot in the middle half has probability at least one half and reduces the retained length to at most three quarters, up to rounding. The expected number of attempts for each such reduction is bounded, so summing expected work over geometric size scales gives expected time. This random-pivot guarantee is not a worst-case guarantee for a deterministic median-of-three heuristic. With duplicates and a strict two-way partition, random pivot choice alone can also fail to shrink an all-equal segment; a three-way partition treats equal keys together.
Quickselect is an efficient algorithm used to find the k-th smallest (or largest) element in an unordered list. It is related to the Quicksort sorting algorithm and uses a similar partitioning approach.
New to topics? Read the docs here!