# Segregate 0’s and 1 ‘s in array.

Question: Given an array arr[], that contains only 0’s and 1’s. Write a function that separate 0’s and 1’s in the array.

Input: 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1
Output: 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1

Readers are requested to submit their codes in comment section below. The best codes will be published on the website.

Method:

1.Initialize two variables leftIndex and rightIndex to index 0 and N-1.
2.Find first 1 by moving leftIndex from left to right
3.Find first 0 by moving rightIndex from right to left.
4.Swap array[leftIndex] and array[rightIndex].
Repeat above process till rightIndex > leftIndex.

The time complexity for this approach is O(n).

`code`

[code language=”cpp”]

#include <iostream>
using namespace std;

void swap( int *a ,int *b)
{
int temp=*a;*a=*b;*b=temp;
}

int main() {
int i, n,low,high;
cin>>n;int arr[n];
for(i=0;i<n;i++)
cin>>arr[i];
low=0;high=n-1;
while(low<high)
{
if(arr[low]==0 && low<high) low++;
if(arr[high]==1 && low<high) high–;
else
{

if(low<high){
swap(&arr[low],&arr[high]);
low++;
high–;}
}

for(i=0;i<n;i++)
cout<<arr[i]<<endl;
cout<<endl;
return 0;
}
[/code]

### 3 comments on “Segregate 0’s and 1 ‘s in array.”

• Godi

#include
using namespace std;
int main()
{
int n;
printf(“enter the no. of elements”);
scanf(“%d”,&n);
int a[n];

for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
for(int i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}

• Godi

#include
using namespace std;
int main()
{
int n;
printf(“enter the no. of elements”);
scanf(“%d”,&n);
int a[n];

for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
for(int i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}