What is the best way to sort an array of 0s and 1s ?

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example

Input :  {0, 1, 2, 0, 1, 2}
Output : {0, 0, 1, 1, 2, 2}
Input : {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}
Output : {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
 Sort

Sample code in C++

#include <bits/stdc++.h>
using namespace std;

// Function to segregate 0s and 1s
void segregate0and1(intarr[], int n)
{
int count = 0; // Counts the no of zeros in arr

for (inti = 0; i< n; i++) {
if (arr[i] == 0)
count++;
}

// Loop fills the arr with 0 until count
for (inti = 0; i< count; i++)
arr[i] = 0;

// Loop fills remaining arr space with 1
for (inti = count; i< n; i++)
arr[i] = 1;
}

// Function to print segregated array
void print(intarr[], int n)
{
cout<< "Array after segregation is ";

for (inti = 0; i< n; i++)
cout<<arr[i] << " ";
}

// Driver function
int main()
{
intarr[] = { 0, 1, 0, 1, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);

segregate0and1(arr, n);
print(arr, n);

return 0;
}

Output

Array after segregation is 0 0 1 1 1 1

Categorized in:

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,