Segregate 0’s and 1’s and 2’s in array.

June 23, 2019

Given an array with 0’s, 1’s and 2’s, we are segregating the 0’s, 1’s and 2’s.

INPUT

0 1 2 0 1 1 1 1 1 0 1 2 1 0 2 2 2 0 1 2 0 1

OUTPUT

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2

Method 1:-

TIME COMPLEXITY – O(N)
SPACE COMPLEXITY – O(1)

1. Simply create an count_array of size 3 and initialize all the element of the array to be zero.
2. The array element of count_array depicts the number of occurences of index i.
3. Traverse the given array and if we get 0 increment the 0th index of count_array and similarly do for 1 and 2 by incrementing the value count_array of 1st and 2nd index.
4. Finally print the number of 0’s , 1’s and 2’s as many times as the value of element of count_array.

code:-

[code language=” cpp”]

#include <bits/stdc++.h>

using namespace std;

int main()

{

int arr[] = {1,0,2,1,0,1,2,0,1,2,0,1,1,1,0,2,0,2,2,0,1,2};//array

int N = sizeof(arr)/sizeof(arr[0]);//size of array

int count[3]={0};

for(int i=0;i<N;i++)

count[arr[i]]++;//increase the count of that index

for(int i=0;i<3;i++)

for(int j=0;j<count[i];j++)//print that index as many times its value is
cout<<i<<" ";
return 0;
}

[/code]

Method 2:-

The approach we need to follow for segregating 0’s 1’s and 2’s is that we maintain 3 pointers.

code:-

[code language=”cpp”]

#include <iostream>
using namespace std;

void swap(int *a, int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
int main() {
// your code goes here
int i;
int arr[] = {1,0,2,1,0,1,2,0,1,2,0,1,1,1,0,2,0,2,2,0,1,2};

int N=sizeof(arr)/sizeof(arr[0]);
int lo=0;
int mid=0;
int high=N-1;
while(mid<=high)
{
if(arr[mid]==0)
swap(arr[lo++],arr[mid]);
else if(arr[mid]==1)
mid++;
else
swap(arr[mid],arr[high–]);

}

for(i=0;i<N;i++)
cout<<arr[i]<<" ";
cout<<endl;

return 0;
}

[/code]

One comment on “Segregate 0’s and 1’s and 2’s in array.”

Abhishek
#include
using namespace std;
int segregate(int a[],int n)
{
int count1=0;
int count2=0;
for(int i=0;i<n;i++)
{
if(a[i]==0)
{
count1++;
}
if(a[i]==1)
{
count2++;
}
}
for(int i=0;i<count1;i++)
{
a[i]=0;
}
for(int i=count1;i<(count1+count2);i++)
{
a[i]=1;
}
for(int i=(count1+count2);i<n;i++)
{
a[i]=2;
}
}
int main()
{
int a[12]={0,1,2,0,1,2,0,1,2,0,1,2};
int n=sizeof(a)/sizeof(a[0]);
segregate(a,n);
for(int i=0;i<n;i++)
{
cout<<a[i];
}
}
check it out!!

0

Log in to Reply