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) –

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 |
#include <bits/stdc++.h> using namespace std; // Number of elements to be sorted #define N 1000000 // Number of sorting runs #define NUM 5 // perform insertion sort on arr[] void insertionSort(int arr[], int low, int n) { // Start from second element (element at index 0 // is already sorted) for (int i = low + 1; i <= n; i++) { int value = arr[i]; int j = i; // Find the index j within the sorted subset arr[0..i-1] // where element arr[i] belongs while (j > low && arr[j - 1] > value) { arr[j] = arr[j - 1]; j--; } // Note that subarray arr[j..i-1] is shifted to // the right by one position i.e. arr[j+1..i] arr[j] = value; } } int Partition (int a[], int low, int high) { // Pick rightmost element as pivot from the array int pivot = a[high]; // elements less than pivot will be pushed to the left of pIndex // elements more than pivot will be pushed to the right of pIndex // equal elements can go either way int pIndex = low; // each time we finds an element less than or equal to pivot, pIndex // is incremented and that element would be placed before the pivot. for (int i = low; i < high; i++) { if (a[i] <= pivot) { swap(a[i], a[pIndex]); pIndex++; } } // swap pIndex with Pivot swap (a[pIndex], a[high]); // return pIndex (index of pivot element) return pIndex; } void QuickSort(int a[], int low, int high) { // base condition if (low >= high) return; // rearrange the elements across pivot int pivot = Partition(a, low, high); // recurse on sub-array containing elements that are less than pivot QuickSort(a, low, pivot - 1); // recurse on sub-array containing elements that are more than pivot QuickSort(a, pivot + 1, high); } void optimizedQuickSort(int A[], int low, int high) { while (low < high) { // do insertion sort if 10 or smaller if (high - low < 10) { insertionSort(A, low, high); break; } else { int pivot = Partition(A, low, high); // tail call optimizations - recurse on smaller sub-array if (pivot - low < high - pivot) { optimizedQuickSort(A, low, pivot - 1); low = pivot + 1; } else { optimizedQuickSort(A, pivot + 1, high); high = pivot - 1; } } } } // Function to check if arr is sorted in ascending order or not bool isSorted(int arr[]) { int prev = arr[0]; for (int i = 1 ; i < N; i++) { if (prev > arr[i]) { cout << "QuickSort Failed!!"; return false; } prev = arr[i]; } return true; } // main function int main() { int arr[N], dupArr[N]; // seed for random input srand(time(NULL)); // to measure time taken by optimized // and non-optimized Quicksort clock_t begin, high; double time_spent1 = 0.0, time_spent2 = 0.0; // perform Quicksort NUM times and take average for (int i = 0; i < NUM; i++) { // generate random input for (int i = 0; i < N; i++) dupArr[i] = arr[i] = rand()%100000; // Perform non-optimized Quicksort on arr begin = clock(); QuickSort(arr, 0, N-1); high = clock(); if (!isSorted(arr)) { cout << "ERRROR"; } // calculate time taken by Non-Optimized QuickSort time_spent1 += (double)(high - begin) / CLOCKS_PER_SEC; // Perform Optimized Quicksort on dupArr begin = clock(); optimizedQuickSort(dupArr, 0, N-1); high = clock(); if (!isSorted(dupArr)) { cout << "ERRROR"; } // calculate time taken by optimized QuickSort time_spent2 += (double)(high - begin) / CLOCKS_PER_SEC; } cout << "Average time taken by Non-Optimized Quick Sort - " << time_spent1/NUM << endl; cout << "Average time taken by Optimized Quick Sort - " << time_spent2/NUM << endl; return 0; } |

**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:**

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

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