Algorithms
Quickselect
O(n) time on average — each step throws away a whole pile instead of sorting it · O(n²) time in the worst case with unlucky pivots · O(log n) space for the recursive calls.
The idea, in plain English
Quickselect is quicksort's lazier cousin. Quicksort fully sorts both sides of a pivot, the reference item used to split the list. Quickselect only wants one answer — the kth smallest item. After it splits the list into a 'smaller' pile and a 'bigger' pile, it throws away whichever pile cannot hold the answer, and only digs into the one that can.
How it works
- 1Pick a pivot item, and split the rest into two piles: smaller than the pivot, and bigger than or equal to the pivot.
- 2Work out where the pivot itself would land: right after all the 'smaller' items. If that is the position you want, the pivot is the answer.
- 3Otherwise, only search further into whichever pile actually holds the position you want, and ignore the other pile completely.
When you'd use it
Use it to find the kth smallest or largest value, like a median or a 'top 10' cutoff, without sorting the whole list. It is noticeably faster than sorting everything just to read off one position.
Common beginner mistakes
- Forgetting that k is a position, like '3rd smallest', not a value. Mixing those up gives nonsense results.
- Searching into both piles like quicksort does. That defeats the entire point of quickselect, which is to ignore the pile you do not need.
Try it — edit and run
Click the code to edit · press ⌘/Ctrl+↵ to run
Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.
Numbers: 7 2 9 4 1 6
3rd smallest: 4
1st smallest: 1See it in motion
Find the 7th smallest (index 6). Press play.
Not sure this is the right topic? See the learning paths → or where this leads →