Hybrid Quick Sort in C++

Hi guys, today we will learn about Hybrid Quick Sort Algorithm in C++ language. Hybrid means when more than one algorithm is used together.

So, we will try to see Insertion Sort and Quick Sort together.

Hybrid Quick Sort

Quick sort works efficiently for a large number of inputs. Whereas, Insertion sort is efficient for less number of inputs because less number of swaps are needed.
So, we will try to merge both of them together and create another algorithm called Hybrid Quick Sort which will solve this problem.

The approach used in Insertion sort is that it divides the given array into 2 parts i.e. sorted in the beginning and unsorted in the end. For every next element, it moves the element to its correct position using swapping.

Similarly, the approach used by Quick sort is that it assumes any element as a pivot and places it to the correct index. And moves all the elements smaller than a pivot at the left and larger elements to its right.

Now, let us see the C++ code implementation for the Hybrid Quick Sort and then I will explain it.

#include<bits/stdc++.h>
using namespace std;
int partition(int arr[], int start_index, int end_index)
{
    int pivot = arr[end_index] ;
    int i ,j;
    i = start_index;
    j = start_index;

    for (int i = start_index; i < end_index; i++)
    {
        if(arr[i]<pivot)
        {
            int var = arr[i];
            arr[i] = arr[j];
            arr[j] = var;
            j += 1;
        }
  }
  int var = arr[j];
  arr[j] = arr[end_index];
  arr[end_index] = var;

    return j;
}
void insertion_sort(int arr[], int start_index, int n)
{

  for(int i=start_index+1;i<n+1;i++)
  {
             int value = arr[i] ;
             int j = i ;
             while (j>start_index && arr[j-1]>value)
             {
                 arr[j]= arr[j-1] ;
                 j-= 1;
             }
             arr[j]= value ;
  }
}
void quick_sort(int arr[], int start_index,int end_index)
{
    if (start_index < end_index)
    {
        int pivot = partition(arr, start_index, end_index);
        quick_sort(arr, start_index, pivot-1) ;
        quick_sort(arr, pivot + 1, end_index) ;
    }
}
void hybrid_sort(int arr[], int start_index, int end_index)
{
    while (start_index < end_index)
    {
        if (end_index-start_index + 1 < 10)
        {
            insertion_sort(arr, start_index, end_index);
            break;
        }
        else
        {
            int pivot = partition(arr, start_index, end_index) ;
            if (pivot-start_index<end_index-pivot)
            {
                hybrid_sort(arr, start_index, pivot - 1);
                start_index = pivot + 1;
            }
            else
            {
                hybrid_sort(arr, pivot + 1, end_index);
                end_index = pivot-1;
            }
        }

    }
}
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];

    hybrid_sort(arr, 0, n-1);

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

First of all, I asked the user to enter the size of the array. Then ask the user to enter the elements of the array.
After taking the input, I called the hybrid_sort(). It checks the size of the array. If it finds to be more than 10, then it calls the quick_sort(). And, if it finds to be less than 10, it calls for insertion_sort().

The approach used in this code is that first assume any element as a pivot and hence place it at the correct index.
Then, move all the elements greater than pivot at the right and smaller to its left. Then sort the side which is having less than 10 elements using insertion sort.

Input:

12
3 7 9 1 2 8 10 5 6 11 4 12

Output:

1 2 3 4 5 6 7 8 9 10 11 12

You can learn more about quick sort and insertion sort from the links mentioned in the starting of the article.

Leave a Reply

Your email address will not be published. Required fields are marked *