Quickselect (k-th Smallest)
DSA · Classic Algorithms
Theory
Quickselect finds the k-th smallest element in an unsorted array without sorting the whole array. It uses the same partition step as Quick Sort: choose a pivot, move smaller elements to its left and larger ones to its right, so the pivot ends up in its final sorted position. If that position equals k, you are done; if k is smaller, you only need to continue in the left part, otherwise in the right part. Because it recurses into just one side, the average running time is O(n) instead of O(n log n) for sorting. The worst case is O(n^2) with consistently bad pivots, which a random pivot makes very unlikely. It is the standard way to find medians and percentiles.
Why we use it
Finding the median, the k-th largest score or a percentile is common in analytics and interviews, and Quickselect does it in linear time on average.
When to use it
Use it for a single order statistic on a large unsorted array. Use a heap when you need the top k items, or sorting when you need everything in order.
How it works
- Choose a random pivot
- Partition around it; pivot lands at index p
- p == k? Yes: Return arr[p]. No: Choose a side.
- k < p? Yes: Search left part. No: Search right part.
- Average O(n)
Syntax
partition around pivot -> index p
if p == k: return a[p]
if k < p: search left else search right
Average O(n), worst O(n^2)Example
import random
def quickselect(nums, k):
"""Return the k-th smallest (0-based)."""
nums = nums[:]
lo, hi = 0, len(nums) - 1
while True:
pivot_index = random.randint(lo, hi)
nums[pivot_index], nums[hi] = nums[hi], nums[pivot_index]
pivot, store = nums[hi], lo
for i in range(lo, hi):
if nums[i] < pivot:
nums[i], nums[store] = nums[store], nums[i]
store += 1
nums[store], nums[hi] = nums[hi], nums[store]
if store == k:
return nums[store]
if k < store:
hi = store - 1
else:
lo = store + 1
salaries = [72000, 45000, 98000, 61000, 120000, 53000, 87000]
print("Smallest:", quickselect(salaries, 0))
print("Median:", quickselect(salaries, len(salaries) // 2))
print("2nd highest:", quickselect(salaries, len(salaries) - 2))
print("Check with sort:", sorted(salaries))Key points
- Partition like Quick Sort, then recurse into one side only
- Average O(n), worst case O(n^2)
- Random pivots avoid the worst case in practice
- Standard way to get medians and percentiles