Introduction

Suppose you have a million exam scores and you want to know the median — the one sitting exactly in the middle. The obvious approach is to sort everything and pick the middle element, but that costs O(nlog⁡n)O(n \log n) time. You're sorting elements you'll never need just to find one.

Quickselect is the algorithm that says: don't bother. Pick a pivot, partition the array around it, and you immediately know whether the element you want is to the left, to the right, or right where the pivot landed. Recurse into only the relevant half — throw the other half away entirely.

The result is expected O(n)O(n) time: linear, not linearithmic. Tony Hoare described the idea in 1961 — the same insight that gave us Quicksort — and it remains one of the most elegant tricks in classical algorithms.

The key tension in selection problems is that checking whether a value is the k-th smallest requires seeing the whole array (O(n)O(n)), while full sorting overshoots by a factor of log n. Quickselect threads the needle exactly in between.

Try It

The array below is shuffled. Use Step to watch Quickselect home in on the median (rank 8 out of 15 elements) one partition at a time. The pivot lands in its final position and the algorithm recurses into only the side that can contain the target rank.

<div class="controls">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-auto" type="button">Auto</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
  <span id="target-label" class="target-label">Finding: <b>median (rank 8)</b></span>
</div>
<div id="array-vis" class="array-vis"></div>
<div id="legend" class="legend">
  <span class="leg-item"><span class="dot active"></span>Active region</span>
  <span class="leg-item"><span class="dot pivot"></span>Pivot</span>
  <span class="leg-item"><span class="dot lo"></span>≤ pivot</span>
  <span class="leg-item"><span class="dot hi"></span>> pivot</span>
  <span class="leg-item"><span class="dot found"></span>Found!</span>
</div>
<div id="status" class="status">Press <b>Step</b> to begin.</div>
<div id="cost-bar" class="cost-bar">
  <div class="cost-label">Elements touched: <span id="touched-count">0</span> / <span id="total-count">15</span></div>
  <div class="bar-track"><div id="bar-fill" class="bar-fill"></div></div>
  <div class="cost-note" id="sort-note">Full sort would touch all <span id="sort-n">15</span> × log₂(15) ≈ <span id="sort-cost">59</span></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; gap: .5rem; align-items: center; flex-wrap: wrap; margin-bottom: .8rem; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.target-label { font-size: .85rem; color: #555; margin-left: .4rem; }
.array-vis { display: flex; gap: 4px; flex-wrap: wrap; margin-bottom: .7rem; align-items: flex-end; }
.cell { display: flex; flex-direction: column; align-items: center; }
.bar { width: 28px; border-radius: 4px 4px 0 0; transition: height .25s, background .25s; }
.val { font: 700 11px ui-monospace, monospace; margin-top: 2px; }
/* color states */
.bar.inactive { background: #d1d5db; }
.bar.active   { background: #93c5fd; }
.bar.pivot    { background: #f59e0b; }
.bar.lo       { background: #6ee7b7; }
.bar.hi       { background: #fca5a5; }
.bar.found    { background: #22c55e; }
.legend { display: flex; gap: .8rem; flex-wrap: wrap; font-size: .78rem; color: #555; margin-bottom: .5rem; }
.leg-item { display: flex; align-items: center; gap: 4px; }
.dot { width: 12px; height: 12px; border-radius: 3px; display: inline-block; }
.dot.active { background: #93c5fd; }
.dot.pivot  { background: #f59e0b; }
.dot.lo     { background: #6ee7b7; }
.dot.hi     { background: #fca5a5; }
.dot.found  { background: #22c55e; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.5em; margin-bottom: .5rem; }
.status.ok { color: #15803d; }
.cost-bar { background: #f1f5f9; border-radius: 8px; padding: .6rem .8rem; }
.cost-label { font-size: .82rem; color: #334155; margin-bottom: .3rem; }
.bar-track { background: #cbd5e1; border-radius: 4px; height: 8px; overflow: hidden; }
.bar-fill { background: #3b82f6; height: 100%; width: 0; border-radius: 4px; transition: width .3s; }
.cost-note { font-size: .78rem; color: #64748b; margin-top: .3rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Quickselect demo: find the median (rank k=8 out of 15 elements, 0-indexed rank 7)
// in expected O(n) time. We use Lomuto partition for clarity.
const N = 15;
const TARGET_RANK = 7; // 0-indexed; median of 15 = index 7

// Deterministic shuffle so the demo starts the same each load (Fisher-Yates with seed).
function seededRng(seed) {
  let s = seed;
  return function() { s = (s * 1664525 + 1013904223) & 0xffffffff; return (s >>> 0) / 4294967296; };
}
function shuffle(arr, rng) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(rng() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

let arr, lo, hi, touchedTotal, state, done, autoTimer;
// state encodes the stage within a single recursive call:
//   { lo, hi, pivotIdx, partIdx, k }
//   partIdx tracks where Lomuto partition is up to
let stepStack; // stack of pending recursive calls: [{lo, hi, k}]
let currentCall; // the call we are currently partitioning

function init() {
  if (autoTimer) { clearInterval(autoTimer); autoTimer = null; }
  arr = Array.from({length: N}, (_, i) => i + 1);
  const rng = seededRng(42);
  shuffle(arr, rng);
  lo = 0; hi = N - 1;
  touchedTotal = 0;
  done = false;
  stepStack = [{ lo: 0, hi: N - 1, k: TARGET_RANK }];
  currentCall = null;
  state = 'idle'; // 'idle' | 'partitioning' | 'done'
  render('idle');
  document.getElementById('btn-step').disabled = false;
  document.getElementById('btn-auto').disabled = false;
}

// colorMap[i] = 'inactive' | 'active' | 'pivot' | 'lo' | 'hi' | 'found'
function buildColorMap(partInfo) {
  const colors = Array(N).fill('inactive');
  if (!partInfo) {
    if (stepStack.length > 0) {
      const top = stepStack[stepStack.length - 1];
      for (let i = top.lo; i <= top.hi; i++) colors[i] = 'active';
    }
    return colors;
  }
  const { lo: plo, hi: phi, pivotPos, scanIdx, partSplit } = partInfo;
  for (let i = plo; i <= phi; i++) {
    if (i === pivotPos) colors[i] = 'pivot';
    else if (partSplit !== undefined && i < partSplit) colors[i] = 'lo';
    else if (scanIdx !== undefined && i <= scanIdx && i !== pivotPos) colors[i] = 'hi';
    else colors[i] = 'active';
  }
  return colors;
}

function render(statusText, statusClass, partInfo, foundIdx) {
  const vis = document.getElementById('array-vis');
  const maxVal = N;
  const maxH = 90;
  const colors = foundIdx !== undefined
    ? Array(N).fill('inactive').map((_, i) => i === foundIdx ? 'found' : 'inactive')
    : buildColorMap(partInfo);

  vis.innerHTML = '';
  arr.forEach((v, i) => {
    const cell = document.createElement('div'); cell.className = 'cell';
    const bar = document.createElement('div');
    bar.className = 'bar ' + (colors[i] || 'inactive');
    bar.style.height = Math.round((v / maxVal) * maxH) + 'px';
    const lbl = document.createElement('div'); lbl.className = 'val'; lbl.textContent = v;
    cell.appendChild(bar); cell.appendChild(lbl);
    vis.appendChild(cell);
  });

  const s = document.getElementById('status');
  s.innerHTML = statusText || '';
  s.className = 'status ' + (statusClass || '');

  const touched = document.getElementById('touched-count');
  touched.textContent = touchedTotal;
  const fill = document.getElementById('bar-fill');
  fill.style.width = Math.min(100, Math.round(touchedTotal / N * 100)) + '%';
}

// Returns the final pivot index after Lomuto partition of arr[plo..phi]
// using the last element as pivot. Mutates arr.
function lomutoPartition(plo, phi) {
  const pivot = arr[phi];
  let i = plo - 1;
  for (let j = plo; j < phi; j++) {
    touchedTotal++;
    if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; }
  }
  [arr[i + 1], arr[phi]] = [arr[phi], arr[i + 1]];
  return i + 1;
}

function step() {
  if (done) return;

  // If no current call is in progress, pop the stack.
  if (currentCall === null) {
    if (stepStack.length === 0) { done = true; return; }
    currentCall = stepStack.pop();
    if (currentCall.lo >= currentCall.hi) {
      // Single element: it must be the answer.
      touchedTotal++;
      done = true;
      render(fmt('<span class="ok">Found median = %v% at index %lo% in %touchedTotal% comparisons!</span>', { v: arr[currentCall.lo], lo: currentCall.lo, touchedTotal: touchedTotal }), 'ok', null, currentCall.lo);
      document.getElementById('btn-step').disabled = true;
      document.getElementById('btn-auto').disabled = true;
      if (autoTimer) { clearInterval(autoTimer); autoTimer = null; }
      return;
    }
    render(fmt('Partitioning active region [%lo%…%hi%] — pivot = %v%', { lo: currentCall.lo, hi: currentCall.hi, v: arr[currentCall.hi] }), '',
      { lo: currentCall.lo, hi: currentCall.hi, pivotPos: currentCall.hi });
    return;
  }

  // Execute the partition for currentCall.
  const { lo: plo, hi: phi, k } = currentCall;
  touchedTotal += (phi - plo + 1);
  const pivotIdx = lomutoPartition(plo, phi);

  if (pivotIdx === k) {
    done = true;
    render(fmt('<span class="ok">Found median = %v% at index %pivotIdx% — took %touchedTotal% total comparisons!</span>', { v: arr[pivotIdx], pivotIdx: pivotIdx, touchedTotal: touchedTotal }), 'ok', null, pivotIdx);
    document.getElementById('btn-step').disabled = true;
    document.getElementById('btn-auto').disabled = true;
    if (autoTimer) { clearInterval(autoTimer); autoTimer = null; }
    currentCall = null;
    return;
  } else if (k < pivotIdx) {
    stepStack.push({ lo: plo, hi: pivotIdx - 1, k });
    render(fmt('Pivot %v% landed at index %pivotIdx%. Target rank %k%%v2% is in the LEFT half [%plo%…%v3%]. Right side discarded.', { v: arr[pivotIdx], pivotIdx: pivotIdx, k: k, v2: 1, plo: plo, v3: pivotIdx-1 }), '',
      { lo: plo, hi: pivotIdx - 1, pivotPos: pivotIdx });
  } else {
    stepStack.push({ lo: pivotIdx + 1, hi: phi, k });
    render(fmt('Pivot %v% landed at index %pivotIdx%. Target rank %k%%v2% is in the RIGHT half [%pivotIdx%%v2%…%phi%]. Left side discarded.', { v: arr[pivotIdx], pivotIdx: pivotIdx, k: k, v2: 1, phi: phi }), '',
      { lo: pivotIdx + 1, hi: phi, pivotPos: pivotIdx });
  }
  currentCall = null;
}

document.getElementById('btn-step').addEventListener('click', step);
document.getElementById('btn-auto').addEventListener('click', function() {
  if (autoTimer) { clearInterval(autoTimer); autoTimer = null; this.textContent = 'Auto'; return; }
  this.textContent = 'Pause';
  autoTimer = setInterval(() => { if (done) { clearInterval(autoTimer); autoTimer = null; document.getElementById('btn-auto').textContent = 'Auto'; return; } step(); }, 900);
});
document.getElementById('btn-reset').addEventListener('click', () => { document.getElementById('btn-auto').textContent = 'Auto'; init(); });

// init cost bar labels
document.getElementById('total-count').textContent = N;
document.getElementById('sort-n').textContent = N;
document.getElementById('sort-cost').textContent = Math.round(N * Math.log2(N));

init();
Result
Console

Notice how the active region (highlighted in blue) shrinks after every step — often dramatically. Elements outside the active region are already eliminated: they can't be the median. Compare that to sorting, which would rearrange every element before declaring a winner.

The Real Complexity

How fast is Quickselect, precisely?

  • Best case O(n)O(n): the very first pivot lands exactly at rank k. One pass, done.
  • Average / expected case O(n)O(n): with a random pivot, each partition shrinks the active region by a constant fraction on average. Summing the geometric series gives n + n/2 + n/4 + … = 2n work — truly linear.
  • Worst case O(n2)O(n^{2}): if every pivot is always the smallest or largest element (e.g. sorted input with a naive first-element pivot), the active region shrinks by only one element per step — just like slow Quicksort.
  • Space: O(1)O(1) extra (in-place), or O(log⁡n)O(\log n) stack frames for the recursive formulation.

The worst case is not academic. A random shuffle before running Quickselect makes it vanishingly unlikely, but adversarial inputs can still trigger it.

The BFPRT fix (1973): Manuel Blum, Robert Floyd, Vaughan Pratt, Ron Rivest, and Robert Tarjan showed you can guarantee O(n)O(n) worst case using median of medians — divide into groups of 5, find each group's median, recursively select the median of those medians, and use it as the pivot. The pivot is guaranteed to land between the 30th and 70th percentile, giving a guaranteed geometric shrinkage. In practice BFPRT is slower than randomized Quickselect due to constants, but it proves linear worst-case selection is achievable.

This places the selection problem firmly in the solved column: O(n)O(n) expected (randomized Quickselect, Hoare 1961) and O(n)O(n) worst case (BFPRT, 1973). Unlike sorting — where Ω(n log n) is a hard lower bound for comparison-based algorithms — selection can genuinely be done in linear time.

Where It Matters

Whenever you need a rank but not a full sorted order, Quickselect (or a cousin) is the tool:

  • Statistics and data science: computing medians, quartiles, and percentiles over large datasets without sorting — critical for streaming analytics where latency matters.
  • Database engines: SELECTTOPkSELECT TOP k, ORDER BY … LIMIT k, and index-free percentile aggregates rely on linear-time selection internally.
  • Computer graphics: finding the median cut for k-d tree construction or the median color for image quantization.
  • Machine learning: choosing the median split in decision trees and finding the k nearest neighbors efficiently.
  • Competitive programming: the "k-th smallest in an array" template problem — Quickselect is the standard O(n)O(n) answer.
  • Operating systems: real-time scheduling sometimes needs the k-th deadline without sorting a full queue.

The deeper lesson: many problems that seem to require sorting actually only require selection, and that distinction saves a log n factor. Recognizing which you need is one of the sharpest tools in an algorithm designer's kit.

See also sorting's lower bound for why selection can be faster, and median-of-medians vs randomized selection for the full picture.

Conclusion

Quickselect distills a core principle of good algorithm design: only do the work you need. Sorting is the sledgehammer that orders everything; Quickselect is the scalpel that reaches straight for the element you want, discarding the rest with every partition.

The expected O(n)O(n) guarantee (Hoare, 1961) is one of the cleanest results in classical computer science. The BFPRT proof (1973) that worst-case O(n)O(n) is also achievable closed the theoretical book on selection. Together they show that knowing which rank you need is worth exactly a factor of log n compared to sorting everything.

Next time you see a "find the median" or "top-k elements" problem, reach for Quickselect — or its streaming variants — and leave the full sort in the toolbox where it belongs.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/quickselect/Content licensed under CC BY-NC 4.0.