Sorting an array containing only 0s and 1s involves rearranging all the elements the array such that all 0’s are grouped together at the beginning, followed by all the 1’s. This kind of problem is also known as “binary array sorting” or “segregate 0s and 1s”.

## Problem Statement

The task is to sort an array that contains only two types of elements: `0`

s and `1`

s. We need to rearrange all the elements in the array such that all the `0`

s come before all the `1`

s.

For example, let’s consider the following unsorted array which contains only `0`

s and `1`

s:

```
[1, 0, 1, 1, 0, 1, 0, 0]
```

The objective is to sort this array so that all `0`

s appear first, followed by all `1`

s. The expected output after sorting would be:

```
[0, 0, 0, 0, 1, 1, 1, 1]
```

This problem is a special case of sorting, where we only have two distinct values. The challenge lies in performing this sorting efficiently, ideally in a single pass through the array.

## Different Approaches

There are many approaches to solve this problem. Below are some of the major ones.

### General Sorting Algorithms

We can use any standard sorting algorithms such as Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, or Quick Sort to segregate zeroes and ones. These algorithms are designed to handle a wide range of sorting tasks and will successfully segregate `0`

s and `1`

s in the array. However, it’s important to note that while these methods will work, they are not specifically optimized for this particular problem.

The time complexity of these standard sorting algorithms varies depending on the chosen method. For instance, simpler algorithms like Bubble Sort, Insertion Sort, and Selection Sort typically have a time complexity of `O(n^2)`

, where `n`

is the number of elements in the array. More efficient algorithms like Merge Sort and Quick Sort offer better performance with a time complexity of `O(n log n)`

. Similarly, the space complexity differs among these algorithms, ranging from `O(1)`

for in-place sorting methods to `O(n)`

for algorithms that require additional memory proportional to the input size. While these general-purpose sorting algorithms will get the job done, there are more efficient approaches specifically tailored to sorting binary arrays of zeroes and ones.

Click here to learn more about different sorting techniques

### Counting Approach (Two Pass Solution)

The main idea behind Counting Approach is to count how many `0`

s and `1`

s are in the array, and then use that information to reconstruct the sorted array.

First, we go through the array once for counting the number of `0`

s and `1`

s. Once we know these counts, we don’t need to do any complex sorting. We can simply fill the beginning of the array with the correct number of `0`

s, and then fill the rest with `1`

s. This approach is faster than traditional sorting methods for this specific case, as it only requires one pass through the array to count, and another pass to fill in the sorted values.

Below is the algorithm for counting approach:

- Initialize two variables,
`zeroes_count`

and`ones_count`

, to keep track of the number of`0`

s and`1`

s in the array. - Traverse the entire array once, incrementing
`zeroes_count`

for each`0`

encountered and`ones_count`

for each`1`

encountered. - Reset a pointer to the beginning of the array.
- Fill the first
`zeroes_count`

positions of the array with`0`

s. - Fill the remaining
`ones_count`

positions of the array with`1`

s. - The array is now sorted with all
`0`

s at the beginning and all`1`

s at the end.

Below is the implementation:

```
def sort_binary_array(arr):
# Initialize counters for zeroes and ones
zeroes_count = 0
ones_count = 0
# Count zeroes and ones in the array
for num in arr:
if num == 0:
zeroes_count += 1
else:
ones_count += 1
# Reset the array with sorted values in-place
for i in range(len(arr)):
if i < zeroes_count:
arr[i] = 0
else:
arr[i] = 1
# No return statement needed as we're modifying the array in-place
# Input array
input_array = [1, 0, 1, 1, 0, 1, 0, 0]
print("Input array:", input_array)
# Sort the array in-place
sort_binary_array(input_array)
print("Sorted array:", input_array)
```

This approach is efficient when compared with regular sorting algorithms, as it requires only two passes through the array - one for counting and one for filling. It has a time complexity of `O(n)`

and requires `O(1)`

space to store counts of zeros and ones.

One limitation of this approach is that it does not work if sorting needs to done based on a particular attribute of an object. For example, let’s say there’s an object with one of it’s attribute as `category`

which can be `0`

or `1`

. Now if we wish to segregate these objects based on `category`

attribute, counting approach can’t be used as we can’t recreate each object just from the counts. The next approach (Two-Pointer Approach) works even for this scenario.

### Two-Pointer Approach (One Pass Solution)

Imagine this: Let’s say you have a line of mixed red and blue balls. Your goal is to arrange them so that all the blue balls are on the left side and all the red balls are on the right side.

To do this efficiently, you can use two people working together from opposite ends of the line. The person on the left (left pointer) looks for red balls and stops when they find one. The person on the right (right pointer) looks for blue balls and stops when they find one. When both people have stopped, they swap the balls they’re holding. This process continues until both the people meet.

In this analogy, blue balls represent `0`

s, and red balls represent `1`

s. The left pointer ensures that everything to its left is `0`

, while the right pointer ensures that everything to its right is `1`

. By working together and swapping when necessary, they efficiently sort the entire array with a single pass through all the elements.

Below is the algorithm:

- Initialize two pointers:
- Set the
`left`

pointer at the beginning of the array (index 0). - Set the
`right`

pointer at the end of the array (last index).

- Set the
- Start a loop that continues while the
`left`

pointer is less than the`right`

pointer: - Inside the loop:
- Move the
`left`

pointer to the right until it finds a 1 or meets the`right`

pointer. - Move the
`right`

pointer to the left until it finds a 0 or meets the ‘left’ pointer.

- Move the
- If the
`left`

pointer is still less than the`right`

pointer:- Swap the elements at the
`left`

and`right`

positions. - Increment the
`left`

pointer. - Decrement the
`right`

pointer.

- Swap the elements at the
- Repeat steps 3-4 until the pointers meet or cross each other.

Below is the implementation:

```
def sort_binary_array(arr):
# Initialize two pointers
left = 0 # Left pointer starts at the beginning of the array
right = len(arr) - 1 # Right pointer starts at the end of the array
# Continue while left pointer is less than right pointer
while left < right:
# Move left pointer to the right until it finds a 1 or meets right pointer
# This helps identify misplaced 1's on the left side
while left < right and arr[left] == 0:
left += 1
# Move right pointer to the left until it finds a 0 or meets left pointer
# This helps identify misplaced 0's on the right side
while left < right and arr[right] == 1:
right -= 1
# If left is still less than right, swap elements and move pointers
# This step ensures 0's move to the left and 1's move to the right
if left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
# Input array
input_array = [1, 0, 1, 1, 0, 1, 0, 0]
print("Input array:", input_array)
# Sort the array in-place
sort_binary_array(input_array)
print("Sorted array:", input_array)
```

The algorithm is efficient as it sorts the array in a single pass, with a time complexity of `O(n)`

where n is the number of elements in the array. It also uses constant extra space, making it space-efficient with `O(1)`

space complexity.

## Applications

The key idea behind this problem of sorting 0s and 1s is similar to binary classification. It can be extended to problems which require elements of one category to be at the beginning of the array and all the elements of another category at the end of the array.

For example, let’s consider the below array:

```
[5, 2, 8, 3, 1, 7, 6, 4]
```

If we need to arrange all even numbers at the start of array and odd numbers at the end of array, we can use the same two pointer algorithm discussed before to do this. It can also be used to solve other problems, such as separating positive and negative numbers, or partitioning an array around a given value (which is a key step in the quicksort algorithm).

The two pointer approach to sort a binary array can be extended to solve the Dutch National Flag problem which involves sorting an array containing elements belonging to 3 distinct categories.