Quickselect

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(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)$ 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)$), while full sorting overshoots by a factor of log n. Quickselect threads the needle exactly in between.

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">{{btn_step}}</button>
  <button id="btn-auto" type="button">{{btn_auto}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <span id="target-label" class="target-label">{{finding_label}}: <b>{{finding_value}}</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>{{leg_active}}</span>
  <span class="leg-item"><span class="dot pivot"></span>{{leg_pivot}}</span>
  <span class="leg-item"><span class="dot lo"></span>{{leg_lo}}</span>
  <span class="leg-item"><span class="dot hi"></span>{{leg_hi}}</span>
  <span class="leg-item"><span class="dot found"></span>{{leg_found}}</span>
</div>
<div id="status" class="status">{{status_initial}}</div>
<div id="cost-bar" class="cost-bar">
  <div class="cost-label">{{cost_label}}: <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">{{sort_note_pre}} <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; }
/* {{c_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; }

// Code not found

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.

How fast is Quickselect, precisely?

• Best case $O(n)$: the very first pivot lands exactly at rank k. One pass, done.
• Average / expected case $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(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)$ extra (in-place), or $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)$ 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)$ expected (randomized Quickselect, Hoare 1961) and $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.

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: $SELECT 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)$ 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.

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)$ guarantee (Hoare, 1961) is one of the cleanest results in classical computer science. The BFPRT proof (1973) that worst-case $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.