Partitioning Algorithms in C++

Hello! Today we are going to study partitioning algorithms in C++. This algorithm is an essential part of the quick sort algorithm. Hence to learn the quick sort algorithm it is necessary to understand the partitioning algorithms. In this post, we are going to learn two such partitioning algorithms namely, naive partition and lomuto partition.

Let us first understand what is a partition is. We have an array of integers and index of the pivot element of the array. We have to partition the given array around the pivot. This means that the elements before the pivot should be less than pivot and the elements after pivot should be greater than the pivot. For example, if the array is {3, 8, 6, 12, 10, 7} and pivot is 7 then after partition the array should become {3, 6, 7, 8, 12, 10}. Note that {6, 3, 7, 12, 8, 10} is also a valid output. Thus any permutation of first two elements {3, 6} and last three elements {8, 10, 12} is acceptable.

Naive Partition

In naive partition, we create a temp array in which we first store the elements which are less than the pivot, and then the elements which greater than the pivot. After creating the temp array we copy the temp array to our original array. Let us see the code implementation of the naive partition.

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

void partition(int arr[], int low, int high, int pivot)
{
    int temp[high-low+1];
    int index=0;
    
    
    for(int i=low;i<=high;i++)  // Putting all the elements < pivot int temp array
        if(arr[i]<=arr[pivot])
            {
                temp[index]=arr[i];
                index++;
            }
    for(int i=low;i<=high;i++) // // Putting all the elements > pivot int temp array
        if(arr[i]>arr[pivot])
            {
                temp[index]=arr[i]; 
                index++;
            }
    for(int i=low;i<=high;i++)
        arr[i]=temp[i-low];
}
 
int main() {
  
    int arr[]={3, 8, 6, 12, 10, 7};
  
  int n=sizeof(arr)/sizeof(arr[0]);
  
  partition(arr,0,n-1,n-1);
  
  for(int i = 0; i<n; i++)
      cout<<arr[i]<<" ";
}

Output –

3 6 7 8 12 10

The naive partition does three traversals of the array and use O(n) extra space. Let us proceed to Lomuto partition which is efficient than the naive algorithm.

Lomuto Partition

In the Lomuto partition the last index of the array is held as a pivot and then the array is partitioned accordingly. We maintain an extra pointer “i” such that all the elements from index low to i are smaller than the pivot. We traverse the array and if we find element less than the pivot element then we increment i and swap the current element with i+1th element. This will be clear once we see the dry run of the code.

Below is our C++ code:

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

void Lomuto(int arr[], int low, int high)
{   
    int pivot=arr[high];
    int i=low-1;
    for(int j=low;j<=high-1;j++){
        if(arr[j]<pivot){
            i++;
            swap(arr[i],arr[j]);
        }
    }
    swap(arr[i+1],arr[high]);
}
 
int main() {
  
    int arr[]={3, 8, 6, 12, 10, 7};
  
  int n=sizeof(arr)/sizeof(arr[0]);
  
  Lomuto(arr,0,n-1);
  
  for(int i=0;i<n;i++)
      cout<<arr[i]<<" ";
}

Output –

3 6 7 12 10 8

Let us see how the above algorithm work.

When we call the Lomuto function we pass the whole array to the function. Hence the array passed is {3, 8, 6, 12, 10, 7}. Before starting, we set the i = low-1 (i = -1) and pivot as the last element arr[h] (pivot = 7). Now we start to iterate over the array.

j=0, we see that 3 < 7 which and we increment i to 0 and we swap 3 with itself. In the end, we have i = 0.
j=1, arr[1] = 8 is greater than 7 hence we do not do anything.
j=2, 6 is less than 7. Thus we do i++ which makes i=1 and swap 8 and 6.
j =3, 12 > 7, we do not do anything.
j=4, 10> 7, we do nothing.

After j=4 we terminate and come out of the loop. After coming out of the loop our array is {3, 6, 8, 12, 10, 7} which is almost partitioned except the pivot (7) is yet to go to its proper place. Hence we swap the pivot and the arr[i+1] (swap 7 and 8) so that we get a fully partitioned array.

Lomuto partition does one traversal of the array hence its time complexity is O(n) and uses constant extra space.

Note – Naive partition is stable whereas Lomuto partition is unstable.

Hope understood the partitioning algorithm. There is another method for partitioning method which is Hoare partition which works better than Lomuto partition on average.

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

Leave a Reply

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