# Hybrid QuickSort Algorithm

Posted in

Vinay Khatri
Last updated on July 13, 2024

## Problem

Implement hybrid quicksort algorithm

### What is a hybrid algorithm?

In a hybrid technique, we combine multiple algorithms and make use of their performance to achieve a result efficiently.

### Approach

In this article, we will combine insertion sort with quicksort algorithm. Insertion sort works well for the arrays with smaller size or when the array “is almost” sorted or sorted. In our implementation, we start with a normal quicksort algorithm and when the size of some subarray falls below some threshold value, we use insertion sort on that subarray. The worst case time complexity of this solution is O(N 2 ) and space complexity is O(N).

### C++ Programming

```#include<bits/stdc++.h>
using namespace std;

void applyInsertionSort(int arr[], int low, int n)
{

for(int i=low+1;i<n+1;i++)
{
int val = arr[i] ;
int j = i ;
while (j>low && arr[j-1]>val)
{
arr[j]= arr[j-1] ;
j-= 1;
}
arr[j]= val ;
}

}

int partition(int arr[], int low, int high)
{
int pivot = arr[high] ;
int i ,j;
i = low;
j = low;

for (int i = low; i < high; i++)
{
if(arr[i]<pivot)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
j += 1;
}
}

int temp = arr[j];
arr[j] = arr[high];
arr[high] = temp;

return j;
}

void applyQuickSort(int arr[], int low,int high)
{
if (low < high)
{
int pivot = partition(arr, low, high);
applyQuickSort(arr, low, pivot-1) ;
applyQuickSort(arr, pivot + 1, high) ;
}
}

void HybridSort(int arr[], int low, int high)
{
while (low < high)
{
if (high-low + 1 < 10)
{
applyInsertionSort(arr, low, high);
break;
}

else

{
int pivot = partition(arr, low, high) ;

if (pivot-low<high-pivot)
{
HybridSort(arr, low, pivot - 1);
low = pivot + 1;
}
else
{
HybridSort(arr, pivot + 1, high);
high = pivot-1;
}
}

}
}

int main()
{
int arr[] = { 2, 9, 40, 67, 88, 8, 15,
6, 5, 4, 26, 4, 6, 52,
45, 23, 90, 18, 49, 8, 23 };
int n = sizeof(arr)/sizeof(arr[0]);
HybridSort(arr, 0, n-1);

for(int i = 0; i < n; i++)
cout << arr[i] << " ";
}```

#### Output

`2 4 4 5 6 6 8 8 9 15 18 23 23 26 40 45 49 52 67 88 90`

### C Programming

```#include<stdio.h>

void applyInsertionSort(int arr[], int low, int n)
{
for(int i=low+1;i<n+1;i++)
{
int val = arr[i] ;
int j = i ;
while (j>low && arr[j-1]>val)
{
arr[j]= arr[j-1] ;
j-= 1;
}
arr[j]= val ;
}
}

int partition(int arr[], int low, int high)
{
int pivot = arr[high] ;
int i ,j;
i = low;
j = low;

for (int i = low; i < high; i++)
{
if(arr[i]<pivot)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
j += 1;
}
}

int temp = arr[j];
arr[j] = arr[high];
arr[high] = temp;
return j;
}

void applyQuickSort(int arr[], int low,int high)
{
if (low < high)
{
int pivot = partition(arr, low, high);
applyQuickSort(arr, low, pivot-1) ;
applyQuickSort(arr, pivot + 1, high) ;
}
}

void HybridSort(int arr[], int low, int high)
{
while (low < high)
{

if (high-low + 1 < 10)
{
applyInsertionSort(arr, low, high);
break;
}

else

{
int pivot = partition(arr, low, high) ;

if (pivot-low<high-pivot)
{
HybridSort(arr, low, pivot - 1);
low = pivot + 1;
}
else
{

HybridSort(arr, pivot + 1, high);
high = pivot-1;
}

}
}
}

int main()
{
int arr[] = { 2, 9, 40, 67, 88, 8, 15,
6, 5, 4, 26, 4, 6, 52,
45, 23, 90, 18, 49, 8, 23 };
int n = sizeof(arr)/sizeof(arr[0]);
HybridSort(arr, 0, n-1);

for(int i = 0; i < n; i++)
printf("%d ",arr[i]);
}```

#### Output

`2 4 4 5 6 6 8 8 9 15 18 23 23 26 40 45 49 52 67 88 90`

### Python Programming

```def applyInsertionSort(arr, low, n):
for i in range(low + 1, n + 1):
val = arr[i]
j = i
while j>low and arr[j-1]>val:
arr[j]= arr[j-1]
j-= 1
arr[j]= val

def partition(arr, low, high):
pivot = arr[high]
i = j = low
for i in range(low, high):
if arr[i]<pivot:
a[i], a[j]= a[j], a[i]
j+= 1
a[j], a[high]= a[high], a[j]
return j

def applyQuickSort(arr, low, high):
if low<high:
pivot = partition(arr, low, high)
applyQuickSort(arr, low, pivot-1)
applyQuickSort(arr, pivot + 1, high)
return arr

def HybridSort(arr, low, high):
while low<high:
if high-low + 1<10:
applyInsertionSort(arr, low, high)
break
else:
pivot = partition(arr, low, high)
if pivot-low<high-pivot:
HybridSort(arr, low, pivot-1)
low = pivot + 1
else:
HybridSort(arr, pivot + 1, high)
high = pivot-1

a = [ 2, 9, 40, 67, 88, 8, 15,
6, 5, 4, 26, 4, 6, 52,
45, 23, 90, 18, 49, 8, 23 ]
HybridSort(a, 0, 20)
print(a)
```

#### Output

`[2, 4, 4, 5, 6, 6, 8, 8, 9, 15, 18, 23, 23, 26, 40, 45, 49, 52, 67, 88, 90]`