AlgoVerse

Quickselect (k-th smallest)

Partition like quick sort, but continue only on the side that holds the k-th item; linear time on average.

To find the k-th smallest item (the median, say) we do not need to sort the whole array. Partition once as in quick sort: the pivot lands in its final place, smaller items on its left and larger ones on its right. If the pivot's rank is k, we are done; otherwise continue on one side only.

Read the full explanation ↓
Input:
n=8 · k=4PDF export

The 4th smallest of eight numbers; only the needed side gets partitioned.

  1. def quickselect(a, k):
  2. lo = 0
  3. hi = len(a) - 1
  4. while True:
  5. if lo == hi:
  6. return a[lo]
  7. p = partition(a, lo, hi)
  8. rank = p - lo + 1
  9. if k == rank:
  10. return a[p]
  11. if k < rank:
  12. hi = p - 1
  13. else:
  14. k = k - rank
  15. lo = p + 1
  18. def partition(a, lo, hi):
  19. pivot = a[hi]
  20. i = lo - 1
  21. for j in range(lo, hi):
  22. if a[j] <= pivot:
  23. i = i + 1
  24. a[i], a[j] = a[j], a[i]
  25. a[i + 1], a[hi] = a[hi], a[i + 1]
  26. return i + 1

Invariant: The answer is always the k-th smallest item of the range a[lo..hi].

Start

3081225314457667k = 4

Local variables

k4

Orange = changed in this step

a list

38251476

Call stack

  1. quickselect()line 1
Step 1 of 66
Black = split · Orange = key stepcompare: 0/11 · swap: 0/8 · split: 0/2 · check: 0/2 · go_left: 0/1 · found: 0/1

    How the work grows with input size

    Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • comparisons
    • current input (n=8)
    01020304046810121416n = number of itemscomparisons
    Show as a table
    ncomparisons
    44.4
    67.4
    813.5
    1020
    1222.1
    1430.6
    1634.6
    Explanation

    The idea

    To find the k-th smallest item (the median, say) we do not need to sort the whole array. Partition once as in quick sort: the pivot lands in its final place, smaller items on its left and larger ones on its right. If the pivot's rank is k, we are done; otherwise continue on one side only.

    Cost

    • On average each partition roughly halves the range: n + n/2 + n/4 + … ≈ 2n, that is O(n), better than sorting (n log n).
    • In the worst case (the "sorted, the smallest" input) each partition removes only one item: O(n²). CLRS builds a guaranteed pivot with the "median of medians" to make even the worst case linear.

    What to watch in the trace

    • The blue band is the range lo..hi that holds the answer; watch it shrink after every partition.
    • k is shown above the array and goes down when the search moves right.