Randomized Quicksort and its Analysis

Key Insight

In practical engineering situations, the assumption that all permutations of input numbers are equally likely might not hold, potentially leading to quicksort's worst-case behavior. To mitigate this, a randomized version of quicksort is introduced. This algorithm incorporates randomization by not always using a fixed element, such as 'A[r]', as the pivot. Instead, it selects a randomly chosen element from the subarray 'A[p .. r]' and swaps it with 'A[r]' before partitioning.

This random sampling technique ensures that the pivot element is equally likely to be any of the 'r-p+1' elements within the current subarray. As a result, the input array's partition is expected to be reasonably well balanced on average, regardless of the initial input order. This randomization strategy effectively transforms the algorithm's worst-case input from a deterministic problem to one where no specific input consistently triggers the worst-case behavior.

While the worst-case running time of randomized quicksort remains Theta(n^2), its expected running time is O(n log n). This is rigorously demonstrated by analyzing the total number of comparisons, 'X', performed during execution. Using indicator random variables, the probability that any two elements 'x[i]' and 'x[j]' are compared is shown to be '2 / (j - i + 1)'. Summing these probabilities across all pairs reveals that the expected number of comparisons 'E[X]' is O(n log n), which directly translates to the algorithm's expected linearithmic running time.