Wednesday, 3 January 2018

C++ Program for Three Way Partitioning - O(n) solution

Three way partitioning refers to divide an array in three parts such as:
1. All the elements smaller than given lower_value should appear first.
2. All the elements between given lower_value and higher_value should come next.
3. All the elements greater than given higher_value should appear in the end.

C++ Program for the three way partitioning of the array is given below. The time and space complexity of the given solution is O(n) and O(1) respectively.

PROGRAM:



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


void threeWayPartition(vector<int> &A,int lowVal,int highVal)
{
     //Your code here
     
     int start=0,end=A.size()-1;
     for(int i=0;i<=end;){
         
            if(A[i]<lowVal){
                  
                  int temp=A[start];
                  A[start]=A[i];
                  A[i]=temp;
                  i++;
                  start++;
            }
            
            else if(A[i]>highVal){
                  
                  int temp=A[end];
                  A[end]=A[i];
                  A[i]=temp;
                  end--;
            }
            else
            {
                i++;
            }
            
           
     }
     
}

int main(){
    
    
      int n;

      cout<<"\nEnter the total number of elements: \n";
      cin>>n;

      cout<<"\nEnter the elements:\n";
      int num;

      std::vector<int> A;

      for(int i=0;i<n;i++){
           cin>>num;
           A.push_back(num);
      }
     
      int lowVal,highVal;

      cout<<"\nEnter the lowVal and highVal respectively: ";
      cin>>lowVal>>highVal;

      cout<<"\n";

      threeWayPartition(A,lowVal,highVal);
      cout<<"\nThe container after three way partitioned: \n";
      for(int i=0;i<A.size();i++) {
           cout<<A[i]<<" ";
      }
      cout<<"\n";
      return 0;
}


OUTPUT:





EmoticonEmoticon