Sort (Segregate) 0s 1s and 2s in an array

Segregate 0s 1s and 2s in an array. Arrange all zeros in first half, all ones in second half and all twos in third half.

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

Example

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

ALGORITHM 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.

C++ Program

#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 cnt[3]={0};//hshing approach
	for(int i=0;i<N;i++)
		cnt[arr[i]]++;//increase the count of that index 
		
	for(int i=0;i<3;i++)
		for(int j=0;j<cnt[i];j++)//print that index as many times its value is
			cout<<i<<" ";
	return 0;
}
Try It

ALGORITHM 2

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

1.    Simply sort the array (using either Heap/Merge sort or using sort() STL function).
2.    Simply print the sorted array.

C++ Program

#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};
	int N = sizeof(arr)/sizeof(arr[0]);
	
	sort(arr,arr+N);//sort the array simply
	for(int i=0;i<N;i++)
		cout<<arr[i]<<" ";
	return 0;
}
Try It


Next > < Prev
Scroll to Top