Offensive Security Researcher & Quantum Cryptography Analyst

Randomized Algorithms: Theory, Analysis, and Implementation in C

Abdul Wahab Junaid
Randomized Algorithms: Theory and Implementation in C

I find randomized algorithms genuinely counterintuitive the first time I encounter them, because they introduce something that feels almost paradoxical: deliberately injecting randomness into a computation to make it more reliable, not less. My favorite way to frame this is through Randomized QuickSort, which I use as my central example in this article — by randomly choosing a pivot instead of always picking, say, the last element, I can take an algorithm with a fragile worst case and turn it into one whose bad behavior becomes vanishingly unlikely on any input, adversarial or not.

History and Background

The formal study of randomized algorithms as a distinct area of computer science developed substantially through the 1970s, with foundational contributions from researchers including Michael Rabin, whose 1976 work on randomized primality testing was one of the field’s landmark early results, and Robert Solovay and Volker Strassen, who independently developed a related randomized primality test around the same time.

Randomized QuickSort itself, which is my focus for the implementation in this article, is a natural extension of Tony Hoare’s original 1959–1961 QuickSort algorithm (which I cover in depth in my dedicated QuickSort article). The randomized variant — choosing a uniformly random pivot at each partitioning step — became a standard technique for taming QuickSort’s worst-case behavior, and it’s discussed extensively in Cormen, Leiserson, Rivest, and Stein’s Introduction to Algorithms, which is where I first studied the formal expected-running-time analysis I present later in this article.

Problem Statement

The general problem randomized algorithms address is this: for many computational problems, a deterministic algorithm’s performance can depend heavily on the specific input it receives, and in the worst case, that performance can be poor — sometimes exploitably so, if an adversary can construct inputs designed to trigger the worst case. Randomized algorithms address this by making some of the algorithm’s internal decisions depend on random choices rather than purely on the input, so that no fixed input can reliably trigger bad performance across repeated runs.

Specifically, for Randomized QuickSort, I want to sort an array of $n$ elements while ensuring that no particular input (including adversarially chosen ones) can force the $O(n^2)$ worst-case behavior with high probability.

Core Concepts

How It Works

For Randomized QuickSort specifically, here’s the process I follow, which differs from standard QuickSort in exactly one step:

  1. If the subarray has fewer than 2 elements, it’s already sorted (base case).
  2. Choose a pivot uniformly at random from the current subarray, rather than always using a fixed position like the last element.
  3. Swap the randomly chosen pivot into the last position of the subarray (so the existing Lomuto partition logic can proceed unchanged).
  4. Partition the subarray around this pivot, exactly as in standard QuickSort.
  5. Recursively apply Randomized QuickSort to the subarray before the pivot.
  6. Recursively apply Randomized QuickSort to the subarray after the pivot.

Working Principle

The internal logic behind why this works relies on a subtle but important shift in perspective: instead of asking “what is the worst-case running time for this specific input?”, I ask “what is the expected running time, averaged over my own random choices, for any input?”

Because the pivot is chosen randomly and independently at each partitioning step, no input — no matter how carefully constructed — can force a bad partition every time. An adversary who doesn’t know (or can’t predict) my random choices cannot reliably construct an array that triggers the $O(n^2)$ behavior; the worst case can still theoretically occur (if I happen to get unlucky with every single random choice), but the probability of that happening becomes vanishingly small as $n$ grows, and the expected running time across all possible sequences of random choices remains $O(n \log n)$.

Mathematical Foundation

I derive the expected running time of Randomized QuickSort using indicator random variables, which I also introduce in more general depth in my dedicated article on that topic.

Let $X$ be the total number of comparisons Randomized QuickSort performs while sorting $n$ distinct elements $z_1 < z_2 < \dots < z_n$ (using $z_i$ to denote the $i$-th smallest element in sorted order). I define an indicator random variable for each pair:

$$ X_{ij} = \begin{cases} 1 & \text{if } z_i \text{ and } z_j \text{ are ever compared} \ 0 & \text{otherwise} \end{cases} $$

so that the total comparisons can be written as:

$$ X = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n} X_{ij} $$

The key probabilistic claim is: $z_i$ and $z_j$ are compared if and only if, among the elements $z_i, z_{i+1}, \dots, z_j$, either $z_i$ or $z_j$ is the first one chosen as a pivot (since choosing anything strictly between them as pivot first would separate them into different partitions before they’re ever compared). Since the pivot at each relevant step is chosen uniformly at random among the elements still under consideration, and there are $j – i + 1$ elements in this range, the probability that $z_i$ or $z_j$ is chosen first among them is:

$$ P(X_{ij} = 1) = \frac{2}{j – i + 1} $$

By linearity of expectation:

$$ E[X] = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \frac{2}{j-i+1} $$

Substituting $k = j – i$ and bounding the resulting sum using the harmonic series $H_n = \sum_{k=1}^{n} \frac{1}{k} \approx \ln n$, this evaluates to:

$$ E[X] = O(n \log n) $$

This confirms that regardless of the input array’s arrangement — sorted, reverse-sorted, or arbitrary — Randomized QuickSort’s expected number of comparisons (and hence its expected running time) is $O(n \log n)$.

Diagrams

Here’s the high-level flow showing where randomness enters the algorithm:

flowchart TD
    A[Unsorted Subarray] --> B{Length less than 2?}
    B -- Yes --> C[Already Sorted, Return]
    B -- No --> D["Choose pivot index uniformly at random"]
    D --> E["Swap random pivot into last position"]
    E --> F["Partition around pivot (Lomuto scheme)"]
    F --> G[Recursively sort left partition]
    F --> H[Recursively sort right partition]
    G --> I[Combined Array is Sorted]
    H --> I

And here’s a diagram contrasting deterministic vs. randomized pivot selection risk:

flowchart LR
    A["Deterministic pivot (e.g., last element)"] --> B["Adversary can construct worst-case input"]
    B --> C["O(n^2) guaranteed on that specific input"]
    D["Randomized pivot"] --> E["No input can reliably trigger worst case"]
    E --> F["O(n log n) expected, regardless of input"]

Pseudocode

RANDOMIZED-QUICKSORT(A, low, high)
    if low < high
        pivotIndex = RANDOMIZED-PARTITION(A, low, high)
        RANDOMIZED-QUICKSORT(A, low, pivotIndex - 1)
        RANDOMIZED-QUICKSORT(A, pivotIndex + 1, high)

RANDOMIZED-PARTITION(A, low, high)
    randomIndex = RANDOM-INTEGER(low, high)   // uniform over [low, high]
    swap A[randomIndex] and A[high]
    return PARTITION(A, low, high)            // standard Lomuto partition

PARTITION(A, low, high)
    pivot = A[high]
    i = low - 1
    for j = low to high - 1
        if A[j] <= pivot
            i = i + 1
            swap A[i] and A[j]
    swap A[i + 1] and A[high]
    return i + 1

Step-by-Step Example

Since the specific execution path of a randomized algorithm depends on the actual random values drawn, I traced my tested C implementation using a fixed random seed (srand(42)) so the result is fully reproducible. I ran it on:

$$ [33, 10, 55, 71, 29, 3, 18] $$

Rather than trace every random pivot choice by hand (which would depend on the specific pseudo-random number generator’s internal sequence), I want to focus on what matters conceptually: at each recursive call, a pivot index is drawn uniformly at random from the current subarray’s range, that element is swapped to the end, and then the exact same Lomuto partitioning logic I describe in my QuickSort article proceeds from there. Regardless of which specific pivots were drawn, the algorithm is guaranteed to terminate with a correctly sorted array, since correctness doesn’t depend on which pivots are chosen — only the performance does.

Running my tested implementation with seed 42 produced the fully sorted output:

$$ [3, 10, 18, 29, 33, 55, 71] $$

which I verified directly by compiling and executing the program.

Time Complexity

Space Complexity

Randomized QuickSort has the same space profile as standard QuickSort:

Correctness Analysis

I want to draw a clear distinction here: the correctness of Randomized QuickSort (that it always produces a sorted array) does not depend on randomness at all — it follows exactly the same partitioning correctness argument I use in my QuickSort article, since randomization only affects which element is chosen as pivot, not the logic of partitioning or recursion itself.

What randomization affects is performance, not correctness. This is precisely what makes Randomized QuickSort a Las Vegas algorithm: it is always correct, and only its running time is a random variable. I find this an important distinction to hold onto, since it’s easy to conflate “randomized” with “probably correct” — for Las Vegas algorithms like this one, correctness is guaranteed; only speed is probabilistic.

Advantages

Disadvantages

Applications

Implementation in C

Here is my tested implementation of Randomized QuickSort:

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

// Swaps two integers via pointers
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Chooses a uniformly random pivot index, swaps it into the last
// position, then performs the standard Lomuto partition
int randomPartition(int arr[], int low, int high) {
    int randomIndex = low + rand() % (high - low + 1);
    swap(&arr[randomIndex], &arr[high]);

    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

void randomizedQuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = randomPartition(arr, low, high);
        randomizedQuickSort(arr, low, pi - 1);
        randomizedQuickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    srand(42); // fixed seed for reproducibility in this demonstration

    int arr[] = {33, 10, 55, 71, 29, 3, 18};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Before sorting: ");
    printArray(arr, n);

    randomizedQuickSort(arr, 0, n - 1);

    printf("After sorting:  ");
    printArray(arr, n);

    return 0;
}

Sample Input and Output

Input:

33 10 55 71 29 3 18

Output (verified by compiling and running the code above, with a fixed seed of 42 for reproducibility):

Before sorting: 33 10 55 71 29 3 18 
After sorting:  3 10 18 29 33 55 71

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version