Hybrid QuickSort Algorithm

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.


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

 
Prerequisites: Insertion Sort, Quick Sort

 
 
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 ten 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 is the C++ program to demonstrate performance of Quick Sort algorithm by hybrid it with insertion sort (and using tail optimizations) –

 

Download   Run Code

Output:

Average time taken by Non-Optimized Quick Sort – 0.0730258
Average time taken by Optimized Quick Sort – 0.0667112

 
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 10 lakh elements 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 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz