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(N ² ) 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:

• Quicksort using Dutch National Flag Algorithm
• Quicksort algorithm using Hoare’s partitioning scheme
• In-place vs out-of-place algorithms
• Rearrange an array in maximum minimum form
• Merge Two Sorted Arrays in-place
• Rod Cutting Problem
• Longest Palindromic Subsequence
• Fibonacci Series
• Circular Doubly Linked List
• Bellman-Ford Algorithm