Segregate 0’s and 1 ‘s in array.

June 23, 2019

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() {
// your code goes here
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]