Quickselect

Tags

Quickselect

Category

Searching

Difficulty

Hard

Problem Statement

Given an unsorted array of integers and an integer k, find the kth smallest element in the array (1-indexed). This is also known as the kth order statistic.

Intuition

Quickselect is a partial sorting algorithm derived from Quick Sort. After partitioning around a pivot, the pivot lands in its final sorted position. If that position equals k-1, we have found our answer. Otherwise, we recurse only into the half that contains the kth element, discarding the other half entirely. This selective recursion is what gives Quickselect its average-case advantage over full sorting.

Approach

  1. Set left = 0 and right = length - 1.
  2. While left <= right:
    • Choose a pivot (e.g., the leftmost element).
    • Partition the subarray so all elements less than the pivot are to its left and all greater are to its right. Let pivotIndex be the pivot's final position.
    • If pivotIndex == k - 1, return the pivot.
    • If pivotIndex < k - 1, search the right subarray (left = pivotIndex + 1).
    • If pivotIndex > k - 1, search the left subarray (right = pivotIndex - 1).

Pseudocode

function quickselect(array, k):
    left = 0
    right = length(array) - 1

    while left <= right:
        pivotIndex = partition(array, left, right)
        if pivotIndex == k - 1:
            return array[pivotIndex]
        else if pivotIndex < k - 1:
            left = pivotIndex + 1
        else:
            right = pivotIndex - 1

function partition(array, left, right):
    pivot = array[left]
    i = left + 1
    j = right

    while i <= j:
        if array[i] > pivot and array[j] < pivot:
            swap(array[i], array[j])
        if array[i] <= pivot:
            i += 1
        if array[j] >= pivot:
            j -= 1

    swap(array[left], array[j])
    return j

Time & Space Complexity

  • Time: O(n) on average. Each recursive step processes roughly half the remaining elements, giving n + n/2 + n/4 + ... = O(2n) = O(n). Worst case is O(n^2) when the pivot is always the min or max.
  • Space: O(1) — the iterative version uses constant extra space. A recursive version uses O(log n) stack space on average.

Key Insights

  • Quickselect only recurses into one partition, unlike Quick Sort which recurses into both. This halving is why the average case is O(n) instead of O(n log n).
  • Pivot selection matters significantly. Random pivot selection or the median-of-medians algorithm can mitigate worst-case behavior.
  • The median-of-medians variant guarantees O(n) worst case but has a larger constant factor and is rarely used in practice.
  • The algorithm modifies the array in place (partial sorting).

Edge Cases

  • k = 1: find the minimum element.
  • k = n: find the maximum element.
  • Array with all identical elements: the pivot always lands correctly; any element is the answer.
  • Array of length 1: return the single element (k must be 1).
  • Already sorted or reverse-sorted arrays: worst case for naive pivot selection.

Linked mentions