QuickSelect: the Kth Element Without Sorting

Sorting to find one element does far more work than the question asked for. QuickSelect answers it in linear time on average by discarding half the data at every step.

The idea

Quicksort partitions around a pivot, then recurses into both halves. But if you only want the element that would end up at index k, you know after partitioning which side it is on - and the other side can be thrown away entirely.

Halving the work each time gives n + n/2 + n/4 + … which sums to 2n. That is the O(n) average.

function quickSelect(items, k) {
  const values = [...items]      // avoid mutating the caller's array
  let left = 0
  let right = values.length - 1

  while (left <= right) {
    // Random pivot: makes adversarial input vanishingly unlikely.
    const pivotIndex = left + Math.floor(Math.random() * (right - left + 1))
    const pivot = values[pivotIndex]
    ;[values[pivotIndex], values[right]] = [values[right], values[pivotIndex]]

    let store = left
    for (let i = left; i < right; i++) {
      if (values[i] < pivot) {
        ;[values[i], values[store]] = [values[store], values[i]]
        store++
      }
    }
    ;[values[store], values[right]] = [values[right], values[store]]

    if (store === k) return values[store]
    if (store < k) left = store + 1
    else right = store - 1
  }

  return undefined
}

const data = [7, 10, 4, 3, 20, 15]
console.log(quickSelect(data, 2))  // 7  — third smallest, zero-indexed
console.log(data)                  // unchanged

The worst case, and the fix

If the pivot is always the smallest or largest remaining element, each pass removes only one item and the cost becomes O(n²). Choosing the pivot at random makes that outcome depend on your random numbers rather than on the input, so no particular input can trigger it.

There is a deterministic O(n) variant - median of medians - but it carries a large constant factor and is rarely worth writing outside a textbook exercise. Knowing it exists is usually enough.

QuickSelect or a heap?

• QuickSelect - O(n) average, O(1) extra space, but needs the whole array in memory and reorders it.
• Min-heap of size k - O(n log k), works on a stream, leaves the input alone.
• Sort - O(n log n), but trivial to write and correct. Fine unless n is large.

For "kth largest in an array" QuickSelect is the strongest answer. For "kth largest in a stream of unknown length" it is not applicable at all, and the heap is the only option.