AlgoVerse

Selection by median of medians

Find the k-th smallest item in linear time even in the worst case: the pivot is the median of the medians of groups of five.

Quickselect is linear on average, but with bad pivots it reaches O(n²). The median of medians (Blum, Floyd, Pratt, Rivest and Tarjan, 1973) picks a pivot that is always good:

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

Seventeen numbers; we want the 4th smallest. The first pivot is 12, the answer lies in the smaller part, and the second pivot, 5, is the answer.

  1. def select(a, k):
  2. # The k-th smallest item (k = 1 is the minimum), in worst-case linear time.
  3. if len(a) <= 5:
  4. a = sorted(a)
  5. return a[k - 1]
  6. groups = [sorted(a[i:i + 5]) for i in range(0, len(a), 5)]
  7. medians = [g[(len(g) - 1) // 2] for g in groups]
  8. pivot = select(medians, (len(medians) + 1) // 2)
  9. low = [x for x in a if x < pivot]
  10. high = [x for x in a if x > pivot]
  11. same = len(a) - len(low) - len(high)
  12. if k <= len(low):
  13. return select(low, k)
  14. if k <= len(low) + same:
  15. return pivot
  16. return select(high, k - len(low) - same)

Invariant: The k-th smallest item of the original array is always the k-th smallest of the current array (with k updated).

Start

120312527318430516227981592710511201211131414215816

Recursion tree

4

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

k4

Orange = changed in this step

a list

123257183012291527520111428

Call stack

  1. select()line 1
Step 1 of 29
Black = pivot · Orange = key stepmedians: 0/2 · small: 0/2 · pivot: 0/2 · split: 0/2 · found: 0/1 · go_low: 0/1
    Explanation

    The idea

    Quickselect is linear on average, but with bad pivots it reaches O(n²). The median of medians (Blum, Floyd, Pratt, Rivest and Tarjan, 1973) picks a pivot that is always good:

    1. Split the array into groups of 5 and find the median of each group.
    2. Recursively find the median of those medians: that is the pivot.
    3. Split the array into smaller than, equal to and larger than the pivot, and continue only in the part that holds the answer.

    Why linear?

    At least half the groups have a median ≥ the pivot, and each of those has at least 3 items ≥ the pivot; so about 3n/10 items are larger and 3n/10 smaller than the pivot, and each part has at most 7n/10 items:

    T(n) ≤ T(n/5) + T(7n/10) + O(n)  ⇒  T(n) = O(n)

    because 1/5 + 7/10 < 1.

    What to watch in the trace

    • The bars are the current call's array; watch how much smaller it gets each time.
    • The call tree has two kinds of calls: one for the medians and one for the part that holds the answer.