1. One-Liner
Quickselect finds the k-th smallest element by partitioning once and recursing only into the half that contains the answer—like binary search on a pivot layout.
2. The Problem It Solves
You need the median, percentiles, or top-k elements without sorting the entire array (O(n log n)). Average time drops to O(n) when partitions are balanced enough.
3. The Core Idea
Pick a pivot, partition so smaller elements are left and larger are right. If the pivot lands at index k, you are done; else recurse left or right only—one subproblem, not two.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Choose pivot | Often last element or random for balance. |
| 2. Partition | Lomuto/Hoare: place pivot in sorted position p. |
| 3. Compare | If p == k, return a[p]. |
| 4. Recurse | If k < p, search left; else search right with adjusted k. |
5. Dry Run Example
Array: [7, 2, 1, 6, 8], k = 2 (0-based 2nd smallest → 6 is wrong; smallest index 2 → third smallest). After partition, pivot index tells which side holds k.
6. Key Properties
| Property | Value |
|---|---|
| Average time | O(n) expected |
| Worst case | O(n²) with bad pivots |
| Space | O(1) iterative + recursion stack |
| In-place | Yes with array partitioning |
7. Where It Is Used
| Domain | Use |
|---|---|
| Statistics | Median, quantiles on streams |
| Libraries | nth_element in C++, selection in standard libs |
8. Interview Tips
Relate to quicksort but single recursion; mention random pivot or median-of-medians for worst-case guarantees.
9. Comparison with Other Algorithms
| Approach | Time | Notes |
|---|---|---|
| Quickselect | O(n) avg | In-place |
| Sort + index | O(n log n) | Simpler, more work |
| Heap (k small) | O(n log k) | Good for top-k heap |
10. Complexity
| Metric | Value |
|---|---|
| Time (Average) | O(n) |
| Time (Worst) | O(n²) naive pivot |
| Space | O(log n) stack typical |
Implementation Example (PYTHON)
import random
def quick_select(nums, k):
def partition(lo, hi):
piv = random.randint(lo, hi)
nums[piv], nums[hi] = nums[hi], nums[piv]
store = lo
for i in range(lo, hi):
if nums[i] < nums[hi]:
nums[store], nums[i] = nums[i], nums[store]
store += 1
nums[store], nums[hi] = nums[hi], nums[store]
return store
lo, hi = 0, len(nums) - 1
while True:
p = partition(lo, hi)
if p == k: return nums[p]
if k < p: hi = p - 1
else: lo = p + 1