Quickselect

O(n) avg

Quickselect reuses quicksort's partition step, but after partitioning it only recurses into the side that contains the position it's looking for — here the median. That makes it O(n) on average (versus O(n log n) to fully sort), and it's the basis of efficient median-finding and 'top-k' selection.

Array
Edit the input and press Play

How it works

  1. Partition the array around a pivot, as in quicksort.
  2. The pivot lands at its final sorted position p.
  3. If p is the target index k, you're done; otherwise recurse into just the side that contains k.
  4. Repeat until the k-th smallest sits in place.

Pseudocode

1quickselect(a, k):                  # O(n) average2  lo ← 0; hi ← n-13  while lo < hi:4    p ← partition(a, lo, hi)         # pivot lands at p (quicksort step)5    if p = k: break6    if p < k: lo ← p+1               # recurse into one side only7    else: hi ← p-18  return a[k]                         # the k-th smallest