Randomized QuickSort

The most prominent randomized algorithm that almost everyone who has taken an algorithms course knows to their heart is the very famous Randomized QuickSort sorting algorithm. Since there are countless resources for this algorithm, I provide this blog to be a foundation for an upcoming post on the detailed analysis of the algorithm.

Procedure

In this procedure, we explore a very simplified version of QuickSort different from the more computationally optimized procedures since we simply wish to explore the theory of QuickSort not the practical effectiveness.

Let’s consider some array $A = [x_1, \ldots, x_n]$ of $n$ elements. Now choose the last element $x_n$ as the pivot denoted by $p$ , i.e. $p = x_n$ . Now collect all the elements in $A$ (excluding $p$ ) that are less than or equal to $p$ , and let this collection be defined by the array $L$ . Similarly, collect all the elements in $A$ (excluding $p$ ) that are strictly greater than $p$ , and let this be the array $R$ . The reason we call $p$ a pivot is because we are essentially pivoting around it to divide the array into $L$ , $p$ , and $R$ .

Now we recurse on both $L$ and $R$ , so that we get $L^*$ and $R^*$ , the sorted versions of $L$ and $R$ . Notice that by how we constructed $L$ and $R$ , we know that all elements in $L^*$ are less than or equal to $p$ and all elements in $R^*$ are strictly greater than $p$ . So the sorted version of $A$ is given by

$\begin{align*} A^* = [L^* \,\, p \,\, R^*] \end{align*}$

which is clearly sorted by our above logic. Thus this both explains the QuickSort algorithm very briefly and proves its correctness.

Now the difficulty with this algorithm is that we want $L$ and $R$ to be balanced in their sizes, and this doesn’t happen if $p = x_n$ is close to the largest element in $A$ . Thus we add in some randomness: choose $p$ randomly from all the elements in $A$ and continue our algorithm with the same procedure. This new algorithm is called Randomized QuickSort whose analysis we touch on below.

Analysis

Firstly, for the deterministic QuickSort algorithm, let the run-time be represented by the function $T(n)$ where $n$ is the number of elements in our given array $A$ . To find $p$ and to combine the $L^*$ , $p$ , and $R^*$ at the end both take a constant amount of time. However, to generate $L$ and $R$ it is known to take linear time, i.e. $O(n)$ time, which follows from the fact that we need to compare every element in $A$ to $p$ (and $A$ has $n$ elements). Thus we see that we can form the following recurrence immediately:

$\begin{align*} T(n) &= T(|L|) + T(|R|) + O(1) + O(n) + O(1) \\ &= T(|L|) + T(|R|) + O(n) \end{align*}$

where $|L|$ and $|R|$ signify the number of elements in $L$ and $R$ , respectively. Also note that in the trivial case of a singleton array, i.e. $n = 1$ , we have $T(1) =1$ since the array is vacuously sorted.

The reason that a more balanced partition of $L$ and $R$ is beneficial is that it produces a recurrence close to the form

$\begin{align*} T(n) &= 2T\lp \frac{n}{2} \rp + O(n) \end{align*}$

which by the Master Theorem (more information can be found here) implies that $T(n) = O(n\log(n))$ which is optimal for a sorting algorithm (why this is asymptotically optimal will be discussed in another post). On the other hand, with a heavily imbalanced partition we produce a recurrence close to the form

$\begin{align*} T(n) &= T(n - 1) + O(n) \end{align*}$

which by the Master Theorem again implies that $T(n) = O(n^2)$ which is definitely not optimal for sorting algorithms. Thus this can provide some little intuition as to why balanced partitions are desired in QuickSort.

Now let’s see how balanced partitions are formed. Notice it is equivalent to say that the $L$ and $R$ are balanced in size and to say that the pivot $p$ is very close to being the median of the array. Thus by choosing a pivot $p$ that has almost an equal number of elements less than or equal to $p$ and greater than $p$ , we can generate a balanced partition as desired.

This observation implies that when our pivot $p$ is very large or small relative to our array $A$ , we have a heavily imbalanced partition. Thus we see that since we choose $p$ as the last element of the array, if we construct our array such that the last element as a maximal or minimal element, the first partition is very imbalanced. For maximum fruition of the worst case, we want this to have at every step of recursion, so this follows that either a sorted or reverse sorted array is the worst case input for deterministic QuickSort (the reason we say “either” is because depending on the implementation of generating the partition, one is a best case and another the worst case). In this case, our recurrence is actually given by

$\begin{align*} T(n) &= T(n - 1) + O(n) \end{align*}$

which we know follows that $T(n) = O(n^2)$ from above, and this is very bad for any sorting algorithm. This concludes that QuickSort has a worst-case time of $O(n^2)$ which is surprising considering the popularity of this algorithm.

However, note that the algorithm we analyzed above is the deterministic version without any randomness, so let’s now see intuitively how randomness could help. Recall that the randomness is added only in the choice of the pivot $p$ which we do randomly rather than always choosing the last element of the array. This now makes it impossible for any specific input to always perform badly, and we also expect our random pivot $p$ to not be maximal or minimal in any sense since it’s random (this is in fact the crux of the randomized analysis of Randomized QuickSort). This provides the intuition as to why randomness might help, and we dive into this in a follow-up post focusing only on the analysis of Randomized QuickSort.

To simply state the result of this randomness, we see that, in fact, our average-case runtime is given by $O(n\log(n))$ which is optimal for sorting algorithms. However, with the same reasoning as for the deterministic algorithm, the worst-case runtime still stands at $O(n^2)$ , but this is known to occur with very low probability. Also with very high probability Randomized Quicksort runs in time $O(n\log(n))$ which makes this algorithm so viable for a sorting algorithm.

The intuitive derivation of these statements has been briefly developed here, but to garner the true scope of the analysis of Randomized QuickSort, I will be writing a follow-up post going into the full mathematics and probabilistic analyses required to achieve the above conclusions.

Recent Posts

Recent Comments

Subscribe

Categories

Archives

Procedure

Analysis

About the Author

Balaram Behera

One thought on “Randomized QuickSort”

Leave a Reply Cancel reply

You may also like these

Analysis of Randomized QuickSort

Key Probabilistic Concentration Bounds

Reservoir Sampling: Uniform Sampling of Streaming Data

Welcome!