Offensive Security Researcher & Quantum Cryptography Analyst

Selection in Expected Linear Time: Randomized Select Algorithm Explained

Abdul Wahab Junaid
Selection in Expected Linear Time: Randomized Select Algorithm

Before I understood the deterministic median-of-medians algorithm, I first learned its simpler, faster-in-practice cousin: randomized select, often called “quickselect.” The core idea is disarmingly simple — it’s basically quicksort, except after partitioning, I only ever recurse into the one side that actually contains the element I’m looking for, throwing away the other side entirely. This one change transforms an $O(n \lg n)$ sorting algorithm into an algorithm that finds a single order statistic in expected $O(n)$ time.

I like presenting this algorithm right alongside median-of-medians because the contrast between them is genuinely illuminating: randomized select is simpler, faster in typical practice, but only offers an expected-time guarantee (with a rare worst case of $O(n^2)$), while median-of-medians is more complex and has larger constant factors, but guarantees $O(n)$ even in the worst case. Understanding both gives me a much fuller picture of the selection problem.

History and Background

Randomized select is a direct descendant of quicksort, both invented by Tony Hoare in 1961 while he was a visiting student at Moscow State University, working on machine translation and needing an efficient sorting method. Hoare’s original quicksort paper, “Algorithm 64: Quicksort,” published in Communications of the ACM in 1961, laid the groundwork for the partitioning scheme that both quicksort and quickselect rely on.

The specific application of this partitioning idea to the selection problem — recursing into only one side rather than both — became a standard technique taught alongside quicksort in essentially every algorithms course and textbook since, and it’s presented as “RANDOMIZED-SELECT” in Cormen, Leiserson, Rivest, and Stein’s “Introduction to Algorithms,” directly preceding their treatment of the deterministic median-of-medians algorithm, precisely to draw the contrast between expected-case and worst-case guarantees.

Problem Statement

Given an unsorted array of $n$ distinct numbers and an integer $i$ (with $1 \le i \le n$), I want to find the $i$-th smallest element — the $i$-th order statistic — as efficiently as possible on average, using randomization to avoid the adversarial worst-case behavior that a naive, non-randomized partitioning strategy would be vulnerable to.

Core Concepts

How It Works

RANDOMIZED-SELECT(A, p, r, i) operates on the subarray A[p..r] and searches for the element with rank $i$ within that subarray:

  1. If p == r (the subarray has only one element), that element must be the answer — return A[p].
  2. Otherwise, choose a pivot uniformly at random from A[p..r], and partition the subarray around it, exactly as in quicksort, yielding a final pivot position q.
  3. Compute the pivot’s rank within the subarray: k = q - p + 1.
  4. If i == k, the pivot itself is the answer — return A[q].
  5. If i < k, recursively search for the i-th element within the left partition, A[p..q-1].
  6. If i > k, recursively search for the (i - k)-th element within the right partition, A[q+1..r] (since the first k elements, including the pivot, are excluded from consideration).

Working Principle

The reason randomization helps here is subtle but important: for any fixed input array, a deterministic pivot-choice strategy (like “always pick the first element”) can be defeated by a specifically crafted adversarial input, causing consistently unbalanced partitions and $O(n^2)$ worst-case behavior. But if the pivot is chosen randomly, there’s no fixed input that can reliably cause bad performance, because the “badness” now depends on the random choices made at runtime, not on the input itself. Averaged over all possible random choices, most pivots turn out to be reasonably good (close enough to the median of the current subarray), which is what drives the expected linear-time bound.

Crucially, only recursing into one side (rather than both, as quicksort does) is what brings the complexity down from $O(n \lg n)$ to $O(n)$: each level of recursion processes a strictly smaller subarray, and because I never need to revisit the discarded side, the total expected work summed across all recursive calls forms a geometric-like series that sums to $O(n)$ rather than the $O(n \lg n)$ that would result from work being duplicated across two recursive branches at every level, as happens in full quicksort.

Mathematical Foundation

Expected running time analysis. Let $T(n)$ denote the expected running time of RANDOMIZED-SELECT on an array of size $n$. Since the pivot is chosen uniformly at random from $n$ elements, each possible resulting partition size is equally likely. If the pivot has rank $q$ (for $q = 1, \dots, n$, each with probability $1/n$), the recursive call operates on a subarray of size $\max(q – 1, n – q)$ in the worst sub-case for that particular pivot rank (I use the larger of the two sides as a conservative upper bound, since I don’t know in advance which side contains rank $i$).

This gives the recurrence:

$$ T(n) \le \frac{1}{n}\sum_{q=1}^{n} T(\max(q-1, n-q)) + O(n) $$

Because each term $\max(q-1, n-q)$ appears either once or twice as $q$ ranges over $1$ to $n$ (depending on whether $n$ is even or odd), this simplifies to:

$$ T(n) \le \frac{2}{n}\sum_{k=\lceil n/2 \rceil}^{n-1} T(k) + O(n) $$

Solving by substitution. I guess $T(n) \le cn$ for a constant $c$, and verify:

$$ T(n) \le \frac{2}{n}\sum_{k=\lceil n/2 \rceil}^{n-1} ck + an $$

Using the formula for the sum of an arithmetic sequence, $\sum_{k=\lceil n/2 \rceil}^{n-1} k$ is approximately $\frac{3n^2}{8}$ for large $n$, giving:

$$ T(n) \le \frac{2c}{n} \cdot \frac{3n^2}{8} + an = \frac{3cn}{4} + an $$

For this to be $\le cn$, I need $\frac{3c}{4} + a \le c$, i.e., $a \le \frac{c}{4}$, which holds for any $c \ge 4a$. This confirms:

$$ T(n) = O(n) $$

so the expected running time is linear, in contrast to the deterministic worst-case bound needed by median-of-medians.

Worst-case bound (for completeness). If the random pivot choices happen to be consistently bad (e.g., always picking the minimum or maximum of the remaining subarray, an event with vanishingly small but non-zero probability), the running time degrades to:

$$ T_{worst}(n) = O(n^2) $$

matching the well-known worst case of quicksort’s partitioning approach, but this occurs with extremely low probability for reasonably large $n$, and does not depend on any particular structure of the input.

Diagrams

flowchart TD
    A[Subarray A p..r, looking for rank i] --> B{p == r?}
    B -->|Yes| C[Return A p - the only element]
    B -->|No| D[Pick random pivot, partition around it]
    D --> E[Compute pivot rank k within subarray]
    E --> F{i == k?}
    F -->|Yes| G[Return the pivot value]
    F -->|No, i < k| H[Recurse into left partition, same i]
    F -->|No, i > k| I[Recurse into right partition, looking for i - k]

Pseudocode

RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)
    exchange A[r] with A[i]
    return PARTITION(A, p, r)

PARTITION(A, p, r)
    x = A[r]
    i = p - 1
    for j = p to r - 1
        if A[j] <= x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i + 1] with A[r]
    return i + 1

RANDOMIZED-SELECT(A, p, r, i)
    if p == r
        return A[p]
    q = RANDOMIZED-PARTITION(A, p, r)
    k = q - p + 1
    if i == k
        return A[q]
    elseif i < k
        return RANDOMIZED-SELECT(A, p, q - 1, i)
    else
        return RANDOMIZED-SELECT(A, q + 1, r, i - k)

Step-by-Step Example

Let me trace RANDOMIZED-SELECT searching for the 4th smallest element ($i = 4$) in the array:

A = [9, 3, 7, 1, 8, 2, 5]   (n = 7)

Suppose the random pivot chosen in the first call happens to be 5 (at index 6, 0-indexed, or position 7, 1-indexed). Partitioning around 5:

k = 4. Since $i = 4 = k$, I return 5 directly — no further recursion needed. This matches the correct answer, since fully sorting A gives [1, 2, 3, 5, 7, 8, 9], and the 4th smallest element is indeed 5.

To illustrate the recursive case too, suppose instead I had been looking for $i = 2$. After the same partition, k = 4, and since $2 < 4$, I’d recurse into the left partition [3, 1, 2] (positions 1 to 3), looking for the 2nd smallest there. A further random pivot choice — say 1 — would partition [3, 1, 2] into [1, 3, 2] roughly (elements $\le 1$ before it, elements $> 1$ after), with 1 at position 1. Since $k = 1 \ne 2$, and $2 > 1$, I’d recurse into the remaining right side [3, 2], looking for the 1st smallest there (since $i – k = 2 – 1 = 1$), which resolves quickly to 2. This matches: the full sorted array’s 2nd smallest is 2.

Time Complexity

Space Complexity

The recursive implementation uses $O(\lg n)$ expected additional space for the recursion call stack, since each recursive call operates on roughly half the previous subarray size in the expected case (though a pathologically unlucky run could use up to $O(n)$ stack space in the rare worst case). The partitioning itself is done in place, requiring no additional array storage beyond a few temporary variables for swapping, so total auxiliary space beyond the input array itself is $O(\lg n)$ expected, $O(n)$ worst case.

Correctness Analysis

Correctness follows the same reasoning as median-of-medians’ correctness argument, since both algorithms share the identical partition-and-recurse structure — only the pivot selection strategy differs. PARTITION correctly guarantees that, after it runs, every element before the returned index is $\le$ the pivot, and every element after is $\ge$ the pivot, regardless of how the pivot itself was chosen. Given this, if the pivot’s rank $k$ within the current subarray equals the target rank $i$, the pivot is trivially the correct answer. Otherwise, since all elements outside the correct partition side are guaranteed (by the partition property) to be on the wrong side of the target rank, it’s always safe to discard them and recurse only into the side that must contain the answer — by induction on subarray size, this recursive narrowing always terminates at the correct element.

The randomization affects only the efficiency of this process, not its correctness — no matter how “bad” the random pivot choices happen to be, the algorithm still always returns the correct order statistic, just potentially more slowly.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int p, int r) {
    int x = arr[r];   /* pivot value, already moved to the end by the caller */
    int i = p - 1;
    for (int j = p; j < r; j++) {
        if (arr[j] <= x) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[r]);
    return i + 1;
}

int randomizedPartition(int arr[], int p, int r) {
    int randomIndex = p + rand() % (r - p + 1);
    swap(&arr[randomIndex], &arr[r]);
    return partition(arr, p, r);
}

/* i is 1-indexed rank within arr[p..r]. */
int randomizedSelect(int arr[], int p, int r, int i) {
    if (p == r) {
        return arr[p];
    }
    int q = randomizedPartition(arr, p, r);
    int k = q - p + 1;   /* rank of the pivot within arr[p..r] */

    if (i == k) {
        return arr[q];
    } else if (i < k) {
        return randomizedSelect(arr, p, q - 1, i);
    } else {
        return randomizedSelect(arr, q + 1, r, i - k);
    }
}

int main(void) {
    srand((unsigned int)time(NULL));

    int arr[] = {9, 3, 7, 1, 8, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    int i = 4;  /* 1-indexed: looking for the 4th smallest element */
    int result = randomizedSelect(arr, 0, n - 1, i);

    printf("The %d-th smallest element is: %d\n", i, result);

    return 0;
}

I deliberately keep i 1-indexed throughout this implementation, matching the pseudocode convention closely, since it makes the correspondence between the code and the mathematical description of “rank” more direct and less error-prone.

Sample Input and Output

Input:
arr = [9, 3, 7, 1, 8, 2, 5]
i = 4 (1-indexed, looking for the 4th smallest element)

Output:
The 4-th smallest element is: 5

Since the pivot choices are randomized, running this program multiple times will exercise different recursive paths internally, but the final answer will always correctly be 5, matching my hand-traced example and the fully sorted array [1, 2, 3, 5, 7, 8, 9].

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version