Hoarse Partitioning Algorithm in C++ (used in quick sorting)

Hello! In this blog, we are going to learn the Hoarse Partitioning Algorithm. Hoarse partitioning is used in the quicksort algorithm. Hence to understand the quick sort algorithm one should have thorough knowledge about partitioning algorithms. There are other partitioning algorithms such as Lomuto partition algorithm.

Before proceeding to the code implementation, we need to understand what partitioning means. Partitioning basically means dividing an array of integer around a given pivot integer. We have to do the dividing with the following rules.

1. All integers after the pivot should be greater than the pivot.
2. All integers before the pivot should be less than the pivot.

Let us see an example.

If the given array of integers is {4, 3, 8, 6, 2, 7, 1} and the pivot integer is 4. After partitioning the array we should get {1, 3, 2, 4, 7, 6, 8} as output. There can be multiple outputs for the given array depending upon the permutation of the numbers.

Let us jump to the code implementation of Hoarse partitioning.

C++ Code for Hoarse Partitioning

Look at the C++ code below:

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

void Hoarse(int arr[], int l, int h)
{   
    int pivot=arr[l];
    int i=l-1,j=h+1;
    while(1){
        do{
            i++;
        }while(arr[i]<pivot);
        do{
            j--;
        }while(arr[j]>pivot);
        if(i>=j)return;
        swap(arr[i],arr[j]);
    }
}
 
int main() {
  
    int arr[]={4,3,8,6,2,7,1};
  
  int n=sizeof(arr)/sizeof(arr[0]);
  
  Hoarse(arr,0,n-1);
  
  for(int i=0;i<n;i++)
      cout<<arr[i]<<" ";
}

Output – 

1 3 2 6 8 7 4

If we take a closer look at the algorithm, we find that it is a very simple algorithm. We fix the pivot as the first element of the array. Now maintain two pointers i and j such that i ranges from low to high and j ranges from high to low. We use two do-while loops. The first do-while loop gives us the element which is less than the pivot and the second do-while loop gives the element greater than the pivot. After this, we swap these elements and move forward. We terminate the loop when i becomes greater than or equal to j.

For example – For the array {4, 3, 8, 6, 2, 7, 1}, we fix the pivot as 4. Now we run the two do-while loops which stop at i=0 and j = 6. We swap the elements and our array becomes {1, 3, 8, 6, 2, 7, 4}. Again we run the do-while loops which stop at i=2 and j=4 and we swap the elements at those indexes. Thus our array becomes {1, 3, 2, 6, 8, 7, 4}. Once again we run the do-while loops which give us i=3 and j=2. Here we terminate the loop as i becomes greater than j.

Note – Hoarse partition and Lomuto partition both are unstable but Horse partition does less work than Lomuto partition on average. Also in Lomuto partition, the pivot element goes to its correct position(after Lomuto partitioning the position of the pivot is same as the position we get if we sort the array) whereas in Hoarse partition pivot does not go to its correct position.

Hope you understood the Hoarse Partitioning algorithm. Thank You.

Check out my other blog posts:-
Knuth-Morris-Pratt (KMP) Algorithm in C++
Rabin Karp Algorithm

One response to “Hoarse Partitioning Algorithm in C++ (used in quick sorting)”

1. bob says:

   May 30, 2022 at 10:02 pm

   His name is Hoare, not Hoarse. There is no ‘s’. You have it spelled wrong.

   Reply