Hybrid QuickSort Algorithm

By | November 16, 2021
Hybrid QuickSort Algorithm

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(N2) 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]

People are also reading:

Leave a Reply

Your email address will not be published.