Quickselect & Order Statistics

Foundations

So far, every lesson produced a fully sorted array. Now, what if you need only one rank, such as the 3rd smallest value, and sorting everything would compute positions nobody reads?

The value of rank k is the one at index k - 1 once the array is sorted; finding it is called an order statistic. Partitioning gets there without sorting: pick a pivot, move every smaller value to its left and every larger one to its right, and the pivot lands at exactly its sorted index. Quickselect then keeps only the side that holds the wanted index and partitions again.

In nums = [7, 1, 5, 3, 6], find the 3rd smallest, sorted index 2. Partition around 5: 1 and 3 move to its left and 7 and 6 to its right, giving [1, 3, 5, 7, 6]. The pivot landed at index 2, the wanted index, so 5 is the answer after one pass of 4 comparisons, even though 7 and 6 are still out of order.

Case Scenario

Kth Largest Element in an Array asks for rank k counted from the top, which is ascending index n - k. For nums = [3, 2, 1, 5, 6, 4] and k = 2, that is index 4. Quickselect partitions toward index 4 and stops when a pivot lands there; random pivots keep the expected work linear even on sorted input. The answer is 5.

The direct approach sorts nums and reads index n - k: O(n log n) to place all 6 values when only one position matters. At ten million values that is over 200 million comparisons, while each partition could have discarded everything on the far side of its pivot.