DSA Quickselect
Quickselect is an algorithm that finds the kth smallest value without sorting the whole list. It partitions the list like quicksort and then keeps only the side that holds the target.
One partition step
A partition moves values smaller than the pivot to its left. The pivot ends at the index it would hold in a sorted list.
def partition(nums, lo, hi, counts):
mid = (lo + hi) // 2
nums[mid], nums[hi] = nums[hi], nums[mid]
pivot = nums[hi]
store = lo
for i in range(lo, hi):
counts[0] += 1
if nums[i] < pivot:
nums[i], nums[store] = nums[store], nums[i]
store += 1
nums[store], nums[hi] = nums[hi], nums[store]
return store
nums = [7, 2, 9, 4, 5, 1, 8]
counts = [0]
pos = partition(nums, 0, len(nums) - 1, counts)
print("list:", nums)
print("pivot index:", pos)
print("comparisons:", counts[0])Keeping one side only
The target index sits in one side of the pivot. The other side is discarded without any more work.
def partition(nums, lo, hi, counts):
mid = (lo + hi) // 2
nums[mid], nums[hi] = nums[hi], nums[mid]
pivot = nums[hi]
store = lo
for i in range(lo, hi):
counts[0] += 1
if nums[i] < pivot:
nums[i], nums[store] = nums[store], nums[i]
store += 1
nums[store], nums[hi] = nums[hi], nums[store]
return store
def quickselect(nums, k):
counts = [0]
lo = 0
hi = len(nums) - 1
while True:
pos = partition(nums, lo, hi, counts)
if pos == k:
return nums[pos], counts[0]
if k < pos:
hi = pos - 1
else:
lo = pos + 1
nums = [7, 2, 9, 4, 5, 1, 8]
value, used = quickselect(nums, 0)
print("smallest:", value)
print("comparisons:", used)Different targets, different counts
Each target stops at a different partition. The counts stay small because whole sides are dropped.
def partition(nums, lo, hi, counts):
mid = (lo + hi) // 2
nums[mid], nums[hi] = nums[hi], nums[mid]
pivot = nums[hi]
store = lo
for i in range(lo, hi):
counts[0] += 1
if nums[i] < pivot:
nums[i], nums[store] = nums[store], nums[i]
store += 1
nums[store], nums[hi] = nums[hi], nums[store]
return store
def quickselect(nums, k):
counts = [0]
lo = 0
hi = len(nums) - 1
while True:
pos = partition(nums, lo, hi, counts)
if pos == k:
return nums[pos], counts[0]
if k < pos:
hi = pos - 1
else:
lo = pos + 1
base = [7, 2, 9, 4, 5, 1, 8, 3, 6]
for k in (0, 8):
value, used = quickselect(list(base), k)
print("k =", k, "value:", value, "comparisons:", used)Example
def partition(nums, lo, hi, counts):
mid = (lo + hi) // 2
nums[mid], nums[hi] = nums[hi], nums[mid]
pivot = nums[hi]
store = lo
for i in range(lo, hi):
counts[0] += 1
if nums[i] < pivot:
nums[i], nums[store] = nums[store], nums[i]
store += 1
nums[store], nums[hi] = nums[hi], nums[store]
return store
def quickselect(nums, k):
counts = [0]
lo = 0
hi = len(nums) - 1
while True:
pos = partition(nums, lo, hi, counts)
if pos == k:
return nums[pos], counts[0]
if k < pos:
hi = pos - 1
else:
lo = pos + 1
base = [9, 3, 7, 1, 8, 2, 6, 5, 4]
print("list:", base)
print("sorted check:", sorted(base))
for k in (0, 4, 8):
value, used = quickselect(list(base), k)
print("k =", k, "value:", value, "comparisons:", used)Key points
- Quickselect finds the kth smallest value without a full sort.
- A partition rearranges one range so the pivot sits at its sorted position.
- The pivot rule here is fixed.
- The pivot is always the middle element of the range.
- Only the side holding the target index is searched again.
- Each partition discards one side, so the average total work grows linearly.
In this example, the kth smallest value is found for three targets in one nine-value list. The pivot is always the middle element of the current range, so every count repeats exactly. The largest value is found after one partition, at a cost of 8 comparisons. The other two targets each need a second, smaller partition. Their totals reach only 16 comparisons. That shrinking work is the average linear behaviour, shown by counts rather than claimed.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
Quickselect has just partitioned a range and the pivot landed at index 5. The target is index 2. What happens next?