Quickselect: Finding the K-th Smallest Element
You have an unsorted array of $n$ elements and you want the $k$-th smallest one -- not the whole sorted array, just that one element.
Describe the Quickselect algorithm. What is its average-case time complexity, and what is the worst case? How can you guarantee the worst case doesn't happen?
Hints
- You do not need to sort the whole array -- just figure out which half of the partition contains rank $k$ and recurse only there.
- After partitioning around a pivot, compare $k$ to the size of the left partition to decide where to recurse. This eliminates one side entirely per step.
- For the expected complexity, set up the recurrence $T(n) = T(n/2) + O(n)$ and recognize it as a geometric series summing to $O(n)$.
Worked Solution
How to Think About It: Quickselect is the selection analog of Quicksort -- same partitioning idea, but instead of recursing on both halves, you only recurse on the half that contains the $k$-th element. That is the insight that drops the complexity from $O(n \log n)$ to $O(n)$ on average. The worst case is the same trap as Quicksort: if you always pick the worst pivot, you do $O(n)$ work per level for $O(n)$ levels, giving $O(n^2)$. The fix is randomization or a clever pivot strategy.
Algorithm:
1. Pick a pivot (randomly, or using median-of-3). 2. Partition the array into three groups: elements less than the pivot, elements equal to the pivot, elements greater than the pivot. 3. Let $L$ = size of the left group, $E$ = size of the equal group. - If $k \leq L$: recurse on the left group. - If $k \leq L + E$: the pivot is the answer. - Otherwise: recurse on the right group with target rank $k - L - E$.
Code:
```python import random
def quickselect(arr, k): """Returns the k-th smallest element (1-indexed).""" if len(arr) == 1: return arr[0] pivot = random.choice(arr) left = [x for x in arr if x < pivot] mid = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] if k <= len(left): return quickselect(left, k) elif k <= len(left) + len(mid): return pivot else: return quickselect(right, k - len(left) - len(mid)) ```
Complexity:
- Average case: $O(n)$. With a random pivot, each level of recursion eliminates a constant fraction of elements in expectation. The recurrence $T(n) = T(n/2) + O(n)$ solves to $O(n)$ by the geometric series.
- Worst case: $O(n^2)$. Occurs when the pivot is always the minimum or maximum -- you reduce the problem by only 1 element per level.
- Guaranteed $O(n)$: Use the median-of-medians algorithm to choose a pivot guaranteed to be within the middle 30-70% of the data. This makes the worst case $O(n)$, though with a larger constant than randomized Quickselect in practice.
Answer: Quickselect runs in $O(n)$ expected time with a random pivot, $O(n^2)$ worst case. Median-of-medians achieves $O(n)$ worst case.
Intuition
The key insight in Quickselect is that selection is strictly easier than sorting. Sorting must process every element at every level of recursion -- you need both halves ordered. Selection only cares about one element's final rank, so you throw away the irrelevant half immediately. That halving at each level is what makes the work geometric: $n + n/2 + n/4 + \cdots = 2n$.
In quant work, this pattern -- 'do I need the full sorted order, or just a quantile?' -- comes up constantly. Computing the median P&L, finding the 95th percentile of a loss distribution, or locating the $k$-th largest position: these are all selection problems, not sorting problems. If your dataset has a million rows and you want the 99th percentile, Quickselect gives you the answer in $O(n)$ instead of $O(n \log n)$. The randomization trick (pick a random pivot) is also a canonical example of how randomness can eliminate worst-case behavior in practice without any additional bookkeeping.