Hybrid QuickSort Algorithm

In this article, hybrid of Quick Sort algorithm with Insertion Sort is discussed to achieve better performance.


 

A Hybrid Algorithm is an algorithm that combines two or more other algorithms that solve the same problem, either choosing one (depending on the data), or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components.

 
Quicksort is one of the fastest sorting algorithms for sorting large data. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort. There have been various variants proposed to boost its performance. Most of them we have already discussed here. Let’s revisit few important optimizations that can be applied to Quicksort.

 
Tail Recursion

To make sure at most O(log n) space is used, recurse first into the smaller side of the partition, then use a tail call to recurse into the other. As such, we successfully sort the array in a way that it minimizes the recursive depth.

 
Hybrid with Insertion Sort

When the number of elements is below some threshold (perhaps 10 elements), switch to a non-recursive sorting algorithm such as insertion sort that performs fewer swaps, comparisons or other operations on such small arrays.

Instead of “many small sorts” optimization, when the number of elements is less than some threshold k, we can simply stop. Later when the whole array has been processed, each element will be at most k positions away from its final sorted position. Now if we perform insertion sort on it, it will take O(kn) time to finish the sort, which is linear as k is a constant.

 
Below are the C++ and Java programs to demonstrate performance of Quick Sort algorithm by hybrid it with insertion sort (and using tail optimizations) –

C++

Download   Run Code

Output:

Average time taken by Non-Optimized Quicksort: 0.0703886
Average time taken by Optimized Quicksort: 0.0665744

Java

Download   Run Code

Output:

Average time taken by Non-Optimized quicksort: 18758732ns
Average time taken by Optimized quicksort: 16959413ns

 
The optimal cut-off for switching from Quicksort to Insertion sort is taken as 10 in above program. As demonstrated by running optimized and non-optimized Quicksort 10 times on 1 million elements (in C++ version) and taking average of time taken by each, we can say without doubt that optimized version is much faster than non-optimized Quicksort.

Note if the input contains many repeated elements, quicksort exhibits poor performance even with optimizations discussed above. To solve this problem, an alternative linear-time partition routine(sometimes called the Dutch national flag problem) 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. We have discussed this approach here.

 
References:

1. https://en.wikipedia.org/wiki/Quicksort
2. https://en.wikipedia.org/wiki/Hybrid_algorithm

 
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 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
Notify of