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() {
// 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]

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;
      }