Randomized Quicksort

As mentioned in , the worst-case scenario for Quicksort is an array that’s already sorted. But there’s an easy way to fix this with a concept that is both ridiculously simple and yet counterintuitive at the same time: before executing Quicksort, you can first shuffle the array.

To shuffle an array means to put its values in random order, similar to shuffling a deck of cards. In Python, you can shuffle an array using the built-in random module:

This modifies array by randomizing the order of its values.

I mentioned that this technique is both simple and counterintuitive at the same time. It’s simple because it attacks the problem head-on. Quicksort is slow when processing a sorted array, so we simply unsort the array before running the rest of the algorithm.

Yet, it’s also counterintuitive since who would have thought to speed up a sorting algorithm by first shuffling the values?

In truth, though, the real counterintuitive idea here is that Quicksort is slow for an array that’s already sorted. One would have thought that we’d have to less work to sort such an array, not more work. However, this is the reality, so shuffling the array does the trick of ensuring that Quicksort will never be slow for any scenario.

I should point out that even shuffling an array isn’t a 100 percent guarantee that Quicksort won’t be slow. It is theoretically possible that shuffling an array will produce the same array again! However, the odds that this might happen are low, and the odds sink further as we deal with larger and larger arrays. The more data there is, the less chance there is that shuffling an array ends up producing the same array again.

Now, shuffling the array does take some time. We’ll analyze how many steps it takes, but take my word for it that preshuffling an array before Quicksort is a lot faster than Quicksorting a presorted array.

If you’re always going to preshuffle the array before performing Quicksort, you can view that as a new step within the Quicksort algorithm. You’re essentially creating a variant of the classic Quicksort algorithm, which doesn’t necessarily preshuffle the array.

As a matter of fact, preshuffling isn’t the only way to use randomization within Quicksort. Another approach is to always choose a random element to serve as the pivot rather than the left- or right-most element. I’m not going to explain this in depth since I don’t want to get back into the weeds of Quicksort right now. However, if you’re interested, the gist of this approach is as follows:

The reason why Quicksort performs badly on a sorted array is that when the array is sorted, the left- or right-most pivot will always end up at the array’s end rather than the center. But by choosing a random pivot, the pivot has a similar chance of landing toward the center whether the array is sorted or not. Again, this explanation will make sense if you recall the details of Quicksort, which you can find in Volume 1, Chapter 13.

In any case, we now have variants of Quicksort to ensure that the sorting will take place in O(N log N) time for all scenarios. Computer scientists refer to these variants as Randomized Quicksort. (It’s nice when computer scientists give an algorithm a name that makes sense.)

When we now compare Mergesort against Randomized Quicksort, it appears that Mergesort no longer has any advantage. The one potential advantage was that Mergesort doesn’t slow down in worst-case scenarios, but now Randomized Quicksort doesn’t either.

We’re still not done pitting these two sorting algorithms against each other, but let’s first spend some time exploring the concept of randomization. In fact, randomization is going to emerge as one of the main themes of the rest of this volume.