Quicksort using Dutch National Flag Algorithm

Implement Quicksort efficiently for inputs containing many repeated elements.

 


 

Quicksort exhibits poor performance for inputs that contain many repeated elements. The problem is clearly visible when all the input elements are equal. Then at each recursion, the left partition is empty (no input values are less than the pivot), and the right partition has only decreased by one element (the pivot is removed). Consequently, the algorithm takes quadratic time to sort an array of equal values.

To solve this problem an alternative linear-time partition routine can be used that separates the values into three groups:

  • values less than the pivot
  • values equal to the pivot and
  • values greater than the pivot.

The values equal to the pivot are already sorted, so only the less-than and greater-than partitions need to be recursively sorted. This linear-time partition routine is similar to three-way Partitioning for Dutch national flag problem.

 
C++ implementation –
 

Download   Run Code

Output:

1 2 2 2 5 6 6 6 6 8

 
The best case for the algorithm now occurs when all elements are equal (or are chosen from a small set of k « n elements). In the case of all equal elements, the modified quicksort will perform at most two recursive calls on empty subarrays and thus finish in linear time.
 

References:
https://en.wikipedia.org/wiki/Quicksort

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂