Hybrid QuickSort Algorithm

Posted in

Hybrid QuickSort Algorithm
vinaykhatri

Vinay Khatri
Last updated on March 29, 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]

    People are also reading:

    Leave a Comment on this Post

    0 Comments