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