Coders Packet

Dutch Flag Algorithm in C++

By Saravanan.V

In this tutorial, we are going to learn how to segregate 0's 1's and 2's in constant space using the Dutch Flag Algorithm in C++.

Dutch Flag Algorithm

We are given an array consists of 0, 1, and 2. We have to segregate the numbers in such a way that all 0's comes in the left of the array, all 1's in middle, and all 2's in right.

Approach for the problem:

The main approach to this problem is to declare three variables(left, mid, right) and making 0's on the left of the left variable, 2's on the right of the right variable, and 1's in the middle.

Algorithm:

1.Take three variables low, mid, right.
2.Initialize left=0, mid=0 and right=size-1.
3.Make a while loop and set the condition as mid<=right.
4.Whenever '0' comes to swap arr[mid] and arr[left] and increment left and mid.
5.Whenever '1' comes just increment mid.
6.Whenever '2' comes to swap arr[mid] and arr[right] and decrement right.

Code snippet to segregate 0's, 1's, and 2's:

int left=0,mid=0,right=n-1; 
while(mid<=right) 
{ 
 if(arr[mid]==0) 
  { 
    swap(arr[left],arr[mid]); 
    left++;mid++; 
  } 
 else if(arr[mid]==1) 
  { 
    mid++; 
  } 
 else if(arr[mid]==2)
  { swap(arr[mid],arr[right]); 
    right--; 
  } 
}

Implementation of the problem:

1.First, declare the array and get the array elements using a loop.

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,i;
  cout<<"Enter the number of elements : \n";
  cin>>n;
  int arr[n];
  cout<<"Enter the elements : \n";
  for(i=0;i<n;i++)
  {
    cin>>arr[i];
  }

2.If the arr[mid]=0, swap with arr[mid] and increment left and mid. By doing this 0's will be on the left of the array. If the arr[mid]=1, just increment mid. So, 1's will be in between the left and mid variable. If arr[mid]=2, swap with arr[right] and decrement right. So, 2's will be in between the mid and right. The main part is when to break the loop when mid<=right because if mid passes the right variable 1's will be on the right of the right variable.

int left=0,mid=0,right=n-1;
while(mid<=right)
 {
  if(arr[mid]==0)
   {
    swap(arr[left],arr[mid]);
    left++;mid++;
   }
  else if(arr[mid]==1)
   {
    mid++;
   }
  else if(arr[mid]==2)
{ swap(arr[mid],arr[right]); right--; } }

3.Print the output.

cout<<"\nSegregated elements are : ";
  for(i=0;i<n;i++)
  cout<<arr[i]<<" ";
}

C++ code to segregate 0's, 1's, and 2's using Dutch Flag Algorithm:

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,i;
  cout<<"Enter the number of elements : \n";
  cin>>n;
  int arr[n];
  cout<<"Enter the elements : \n";
  for(i=0;i<n;i++)
  {
    cin>>arr[i];
  }
  int left=0,mid=0,right=n-1;
  while(mid<=right)
  {
    if(arr[mid]==0)
    {
      swap(arr[left],arr[mid]);
      left++;mid++;
    }
    else if(arr[mid]==1)
    {
      mid++;
    }
    else if(arr[mid]==2){
      swap(arr[mid],arr[right]);
      right--;
    }
  }
  cout<<"Segregated elements are : \n";
  for(i=0;i<n;i++)
  cout<<arr[i]<<" ";
}

Output:

Enter the number of elements: 5
Enter the elements: 1 2 2 1 0
Segregated elements are: 0 1 1 2 2  

 

Download Complete Code

Comments

No comments yet