# Sort an Array of 0s and 1s

Sort an Array of 0s and 1s” is one of the favorite technical interview problem of array data structure. Here, we are given an array of size ‘n’ and our task is to sort this array.

Array contains only 0s and 1s.

Example:

```INPUT:
Arr[5] = {1, 0, 1, 0, 1}
OUTPUT:
Arr[5] = {0, 0, 1, 1, 1}```

There are many methods to sort an array of 0s and 1s. Some of them are:

#### METHOD 1: Brute-force Approach to Sort an Array of 0s and 1s

The brute-force solution of the given problem is to simply sort the array using quick sort or merge sort.

The time complexity of the above problem would be O(nlogn) for sorting.

#### METHOD 2: Count and Replace Approach to Sort an Array of 0s and 1s

This method is more time efficient and requires O(n) time complexity with traversing the array two times only.

In this method, we count the occurrence of 0s as count, and then, we put 0s at the beginning and rest 1s in the array.

### C++ Program to sort an array of 0s and 1s is as follows:

```/* Program to sort an array of 0s and 1s */
#include<bits/stdc++.h>
using namespace std;
int main()
{
/* Scan array size */
int n;
cout<<"Enter array size:";
cin>>n;

/* Scan array elements */
int arr[n];
cout<<"\nEnter array elements:\n";
for(int i = 0; i < n; i++)
cin>>arr[i];

/* Count 0s  */
int count0 = 0;
for(int i = 0; i < n; i++)
{
if(arr[i] == 0)
count0++;
}

/* we put 0s at the beginning and rest 1s in the array */
for(int i = 0; i < count0; i++)
{
arr[i] = 0;
}
for(int i = count0; i < n; i++)
{
arr[i] = 1;
}

/* Print the resultant array */
cout<<"\nThe sorted array is:\n";
for(int i = 0; i < n; i++)
cout<<arr[i]<<" ";
}
```
```OUTPUT:
Enter array size: 5
Enter array elements:
0 1 0 1 0
The sorted array is:
0 0 0 1 1

Time Complexity:
This requires two times traversal of the array.
O(n), where n is the size of the array```

METHOD 3: Two Pointers

The steps required to sort an array of 0s and 1s are as follows:

1. Scan array size.
2. Scan array elements.
3. Set ptr1 = 0 and ptr2 = n-1
4. While(ptr1 < ptr2)
5. while(arr[ptr1] == 0) then ptr1++.
6. while(arr[ptr2] == 1) then ptr2–.
7. If(ptr1 < ptr2) then swap(arr[ptr1],arr[ptr2]) and  ptr1++ ,ptr2–.

### C++ Program to sort an array of 0s and 1s is as follows:

```/* Program to sort an array of 0s and 1s */
#include<bits/stdc++.h>
using namespace std;
int main()
{
/* Scan array size */
int n;
cout<<"Enter array size:";
cin>>n;

/* Scan array elements */
int arr[n];
cout<<"\nEnter array elements:\n";
for(int i = 0; i < n; i++)
cin>>arr[i];

/* Initiate pointers */
int ptr1 = 0, ptr2 = n-1;
while(ptr1 < ptr2)
{
/* Increment ptr1 till we get 0s */
while(arr[ptr1] == 0)
ptr1++;

/* Decrement ptr2 till we get 1s */
while(arr[ptr2] == 1)
ptr2--;

/* swap elements */
int temp = arr[ptr1];
arr[ptr1] = arr[ptr2];
arr[ptr2] = temp;
ptr1++;
ptr2--;
}

/* Print the resultant array */
cout<<"\nThe sorted array is:\n";
for(int i = 0; i < n; i++)
cout<<arr[i]<<" ";
}

```
```OUTPUT:
Enter array size: 5
Enter array elements:
0 1 0 1 0
The sorted array is:
0 0 0 1 1

Time Complexity:
This method requires only one time traversal of array
O(n), where n is the size of the array.```

Related Posts: