Randomized Quick Select

Tony Hoare, 1961

Invented by Tony Hoare in 1961, Quick Select uses random pivot selection and partitioning to find the k-th order statistic in expected linear time. After choosing a random pivot and partitioning the array, the algorithm discards the portion that cannot contain the answer and recurses on the remaining segment. Faded bars are discarded; the coral bar is the pivot; gold marks the scan position.