# Sort an array that contains only 0's and 1's

C++ implementation to sort an array that contains only 0's and 1's.
Submitted by Vikneshwar GK, on January 20, 2022

Consider an array of size n and it contains values only 0's and 1's. For example, if n=5, the array elements can be 0, 1, 1, 0, and 1. The task at hand is to sort this array in a time-efficient manner, i.e., place all the 0's on the left side and 1's on the right side.

Example:

```Input:
test1[] = {1, 1, 0, 1, 0, 0, 0, 1, 1, 0}
Output:
test1[] = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1}

Input:
test1[] = {1, 1, 1, 1, 1, 1, 0, 1, 1, 1}
Output:
test1[] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1}
```

Solution 1: Sorting the array

This is a usual approach to solve this problem, i.e., sorting the given array using an O(nlog(n)) algorithm.

C++ Implementation:

```#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << endl;
}

// Main function
int main()
{
int array[100], N;
cout << "Enter Number of elements: ";
cin >> N;

for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}

// sorting the array
sort(array, array + N);

cout << "Sorted Array" << endl;
printArray(array, N);

return 0;
}
```

Output:

```Enter Number of elements: 5
Enter element 1:0
Enter element 2:0
Enter element 3:1
Enter element 4:1
Enter element 5:0
Sorted Array
0 0 0 1 1
```

Solution 2: Using start and end Pointers

This approach uses two pointers to point the start and end of the array. It involves the following steps:

• Step 1: start=0 and end=length-1
• Step 2: increment start if the array element at start is equal to 0.
• Step 3: if not, swap the elements at start and end, and decrement end.
• Step 4: repeat step 2 and step 3 until start becomes greater than or equal to end.

C++ Implementation:

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

// function to sorting 0 and 1
void sort0and1(int array[], int length)
{
int start = 0;
int end = length - 1;

// loop until start is less than end
while (start < end) {

if (array[start] == 1) {
// swap element at start and end
swap(array[start], array[end]);
end--;
}
else {
start++;
}
}
}

// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << endl;
}

// Main function
int main()
{
int array[100], length;
cout << "Enter Number of elements: ";
cin >> length;

for (int i = 0; i < length; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}

// sorting the array
sort0and1(array, length);

cout << "Sorted Array" << endl;
printArray(array, length);

return 0;
}
```

Output:

```Enter Number of elements: 10
Enter element 1:1
Enter element 2:1
Enter element 3:0
Enter element 4:1
Enter element 5:0
Enter element 6:0
Enter element 7:1
Enter element 8:1
Enter element 9:1
Enter element 10:0
Sorted Array
0 0 0 0 1 1 1 1 1 1
```

Time Complexity: O(n)

As this approach involves simple iteration through the array, the time complexity remains O(n).