How Does Quickselect Find the kth Smallest Element?

Quickselect is a selection algorithm that finds the kth smallest element in an unsorted array in linear average time. Derived from the Quicksort sorting algorithm, it avoids sorting the entire array by partitioning elements around a pivot and recursively searching only the side that contains the target index. This single-branch recursion reduces the average time complexity from linearithmic to linear.

The Partitioning Mechanism

At the core of Quickselect is the partition step, which is identical to the one used in Quicksort. Given an array \(A\) of length \(n\) and a chosen pivot element \(p\), partitioning rearranges the array in place so that:

  • All elements smaller than \(p\) are placed to the left of \(p\).
  • All elements greater than \(p\) are placed to the right of \(p\).
  • The pivot \(p\) is placed at its final sorted index, say \(q\).

This partitioning step takes \(\Theta(n)\) time because every element in the current subarray must be compared to the pivot once.

Searching Only One Side

Once the pivot is placed at index \(q\), Quickselect compares \(q\) with the target index \(k - 1\) (assuming 0-based indexing for the \(k\)-th smallest element):

  • If \(q = k - 1\), the pivot itself is the \(k\)-th smallest element, and the algorithm returns \(A[q]\).
  • If \(q > k - 1\), the \(k\)-th smallest element must lie in the left subarray \(A[0 \dots q-1]\). Quickselect recurses only on this left portion.
  • If \(q < k - 1\), the \(k\)-th smallest element must lie in the right subarray \(A[q+1 \dots n-1]\). Quickselect recurses only on this right portion.

Unlike Quicksort, which recurses on both subarrays, Quickselect discards one side at every step.

Why Average Time Is Linear

When the pivot is chosen uniformly at random, it splits the array into two parts of roughly equal size on average. Even a moderately good pivot reduces the remaining search space by a constant fraction.

If each partition reduces the problem size by a constant factor, such as halving it, the total work across all recursive calls forms a geometric series:

\[T(n) = n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \dots\]

The sum of this geometric series converges to \(2n\), which gives an average time complexity of \(O(n)\).

Worst-Case Behavior

If the pivot is consistently chosen poorly—for example, always picking the smallest or largest element in an already sorted array—the search space only shrinks by one element per step. In this scenario, the work becomes:

\[T(n) = n + (n - 1) + (n - 2) + \dots + 1 = O(n^2)\]

Randomizing pivot selection makes this \(O(n^2)\) worst case exceedingly rare in practice. For applications requiring a strict worst-case guarantee, deterministic pivot-selection methods such as the Median of Medians can be used to achieve \(O(n)\) worst-case time, though with a higher constant factor.