The Quickselect Algorithm

Analogy categoryAnalogies

Introduction

Quickselect is a divide-and-conquer algorithm for finding the k-th smallest (or largest) element in an unordered list without fully sorting it. It is closely related to quicksort: both use a partitioning step around a pivot, but quickselect only recurses into the single partition that contains the desired element, rather than recursing into both halves. This gives quickselect an expected O(n) running time, much faster than sorting the whole array first.

🏏

Cricket analogy: Finding the 5th-highest run scorer in a tournament without fully ranking every batter is like quickselect: partition batters around a pivot score and only dig into the group that must contain the 5th-highest, skipping full sorting for expected O(n) speed.

Algorithm/Syntax

python

import random

def quickselect(arr, k):
    """Return the k-th smallest element (0-indexed) of arr."""
    if len(arr) == 1:
        return arr[0]

    pivot = random.choice(arr)
    lows = [x for x in arr if x < pivot]
    highs = [x for x in arr if x > pivot]
    pivots = [x for x in arr if x == pivot]

    if k < len(lows):
        return quickselect(lows, k)
    elif k < len(lows) + len(pivots):
        return pivot
    else:
        return quickselect(highs, k - len(lows) - len(pivots))

Explanation

Quickselect partitions the array around a randomly chosen pivot into three groups: elements less than the pivot, equal to the pivot, and greater than the pivot. If the target index k falls within the 'lows' group, the algorithm recurses only into 'lows'. If k falls within the 'pivots' group, the pivot itself is the answer. Otherwise, it recurses into 'highs' with an adjusted index. Crucially, only one of the two partitions is explored per recursive call, which is what distinguishes quickselect from quicksort and gives it a smaller expected recurrence T(n) = T(n/2) + O(n) on average, resolving to O(n).

🏏

Cricket analogy: Partitioning batters into those scoring below, equal to, and above a randomly chosen pivot score, then recursing only into the group containing the target rank (say, the 5th-highest), is exactly quickselect's approach, discarding the irrelevant group entirely each round.

Example

python

import random

def quickselect(arr, k):
    if len(arr) == 1:
        return arr[0]
    pivot = random.choice(arr)
    lows = [x for x in arr if x < pivot]
    highs = [x for x in arr if x > pivot]
    pivots = [x for x in arr if x == pivot]
    if k < len(lows):
        return quickselect(lows, k)
    elif k < len(lows) + len(pivots):
        return pivot
    else:
        return quickselect(highs, k - len(lows) - len(pivots))


# Trace for finding the median (k=3, 0-indexed) of:
nums = [7, 10, 4, 3, 20, 15]
# Sorted reference: [3, 4, 7, 10, 15, 20] -> index 3 is 10
random.seed(1)
result = quickselect(nums, 3)
print(result)  # 10

# Finding the minimum (k=0) and maximum (k=len-1) also work:
print(quickselect(nums, 0))          # 3 (minimum)
print(quickselect(nums, len(nums)-1))  # 20 (maximum)

Complexity

With a randomly chosen pivot, quickselect runs in O(n) expected time, because on average each recursive call discards a constant fraction of the remaining elements, giving the recurrence T(n) = T(n/2) + O(n) which sums to O(n) via a geometric series. In the worst case, if the pivot is always the smallest or largest element (e.g. adversarial input against a naive first-element pivot), the algorithm degrades to O(n^2). To guarantee O(n) worst-case time, the median-of-medians algorithm can be used to select a pivot that is provably close to the true median, at the cost of a larger constant factor; this is rarely needed in practice since random pivoting makes worst-case behavior extremely unlikely.

🏏

Cricket analogy: With a randomly chosen pivot batter, finding the k-th highest scorer runs in expected O(n), but if the pivot is always the lowest scorer (adversarial bowling-friendly pitch), it degrades to O(n^2); a median-of-medians pivot guarantees O(n) worst case at extra cost.

Key Takeaways

Quickselect finds the k-th smallest element by partitioning around a pivot and recursing into only one side, unlike quicksort which recurses into both.
Its expected time complexity is O(n), with a worst case of O(n^2) for poor pivot choices.
Random or median-of-three pivot selection keeps the algorithm's expected performance close to O(n) in practice.
The median-of-medians technique guarantees O(n) worst-case time but is rarely used due to higher constant factors.

Practice what you learned

1. What is the key difference between quickselect and quicksort?

2. What is the average-case time complexity of quickselect?

3. What causes quickselect to degrade to O(n^2) in the worst case?

4. What technique guarantees O(n) worst-case time for selection, at the cost of a larger constant factor?

Was this page helpful?

Merge Sort as Divide and Conquer

Closest Pair of Points

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#TheQuickselectAlgorithm#Quickselect#Algorithm#Syntax#Explanation#StudyNotes#SkillVeris