QuickSelect

Imagine you have a disorganized shelf of books and you want the 5th shortest. You don't need to alphabetize the entire shelf — you just need the 5th shortest. Sorting everything is overkill.

QuickSelect is smarter. Pick any book as a pivot. Everything shorter goes left, everything taller goes right. Now the pivot lands in its final sorted position. If that position is exactly 4 (0-indexed, so it's the 5th shortest) — done! If it's at position 7, you only need to look left. If it's at position 2, only look right. Each step, you throw away the half you don't need.

The key difference from QuickSort

QuickSort recurses on both halves — it needs everything sorted. QuickSelect recurses on one half — whichever side contains the kth element. The other half gets completely ignored. That's what turns \(O(n \log n)\) into \(O(n)\).

How the math works out

With a random pivot, it lands near the middle on average, splitting the array roughly in half each time. The work done is n + n/2 + n/4 + n/8 + … This is a geometric series that sums to 2n — so expected total work is \(O(n)\).

The worst case

With a bad pivot every time (always the smallest or largest element), we only eliminate one element per step. Total work: n + (n-1) + (n-2) + … = \(O(n^2)\) — same pathology as QuickSort on sorted input.

The fix: pick the pivot at random. A random pivot makes the catastrophic case astronomically unlikely. If you need a guaranteed \(O(n)\) worst case (say, for adversarial inputs), use Median of Medians instead — at the cost of a larger constant factor.

QuickSelect — Find kth Smallest (0-indexed)

import random

def partition(arr, lo, hi):
    # Random pivot to avoid worst case
    pivot_idx = random.randint(lo, hi)
    arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

def quickselect(arr, lo, hi, k):
    if lo == hi:
        return arr[lo]
    p = partition(arr, lo, hi)
    if p == k:
        return arr[p]
    elif p > k:
        return quickselect(arr, lo, p - 1, k)
    else:
        return quickselect(arr, p + 1, hi, k)

arr = [7, 2, 5, 1, 9, 3]
print(quickselect(arr, 0, len(arr) - 1, 2))  # 3rd smallest = 3

Output

Complexity

⚡ Average case (random pivot)Geometric series: n + n/2 + n/4 + … = 2n total work on average

Linear — expected\(O(n)\)

💀 Worst case (always bad pivot)Sorted input with first/last pivot — eliminates only 1 element per step

Quadratic\(O(n^2)\)

💾 SpaceIn-place partitioning; recursion stack depth is \(O(n)\) worst case but \(O(\log n)\) average

Constant extra memory\(O(1)\)

The key difference from QuickSort

How the math works out

The worst case

QuickSelect — Find kth Smallest (0-indexed)

Complexity

Quick check