Sorting Algorithms in Python — Quicksort worst-case, randomized version and three-way

With the last post, I introduced Quicksort and its Python implementation. At the end of the same post I told you that I would have made an additional post about it to talk about the worst-case scenario and how to avoid poor performances.

Quicksort worst-case

The question I asked you at the end of the post was:

When does the worst-case of Quicksort occur?

We’ve seen that the best-case scenario execution time for Quicksort is O(nlogn) (the same as Merge Sort and Heapsort). To introduce you to the worst-case scenario I want to refresh your mind about the Partition function. Its job is to take a sub-array and divide it into two parts:

• The first part contains the elements ≤ than the pivot;
• The second part contains the element > than the pivot;

You can intuitively understand that the worst-case scenario happens when at every execution of Partition we have sub-arrays of n-1 elements and one with 0 elements. I wanna say again that the convenience provided by the Partition function is that the pivot will be in the correct position. The worst-case scenario, then, happens when the arrays are already sorted (in this case at the end of the Partition execution nothing will be changed and every element will be matched with the pivot).

A possible solution: Randomized version

A solution that is usually adopted is to randomize the choice of the pivot. In this way we obtain the Randomized version (which is pretty similar to the normal one):

Another problem: repeated elements

As I said before Quicksort becomes reeeeally slow when dealing with already sorted arrays. Another situation in which the performance deteriorates is when there are a lot of repeated elements. In this situation, there is a disparity between the sub-arrays because all the elements equal to the pivot will be put into the first sub-array.

Let’s think about the extreme case: all the elements in the array are the same. In this case, we go back to the worst-case scenario.

The solution: Quicksort Three Way

Well, I think you already understand what needs to be done: instead of dividing the array into two parts, we divide it in… three!

• A part that contains elements < than the pivot;
• A part that contains elements = to the pivot;
• A part that contains elements > than the pivot.

I’m tired of all the theory and I will go directly to the code for this time:

Conclusions

It was a needed additional post about my favorite sorting algorithm. Hope you liked it!

As usual, if you want to see the source code you can check my GitHub!