Sort an Array Containing 0's and 1's

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: 0s and 1s. We need to rearrange all the elements in the array such that all the 0s come before all the 1s.

For example, let’s consider the following unsorted array which contains only 0s and 1s:

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

The objective is to sort this array so that all 0s appear first, followed by all 1s. 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 0s and 1s 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 0s and 1s 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 0s and 1s. 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 0s, and then fill the rest with 1s. 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 0s and 1s 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 0s.
Fill the remaining ones_count positions of the array with 1s.
The array is now sorted with all 0s at the beginning and all 1s 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)


#include <stdio.h>
#include <stdlib.h>

void sort_binary_array(int* arr, int size) {
  // Initialize counters for zeroes and ones
  int zeroes_count = 0;
  int ones_count = 0;
  
  // Count zeroes and ones in the array
  for (int i = 0; i < size; i++) {
    if (arr[i] == 0) {
      zeroes_count++;
    } else {
      ones_count++;
    }
  }
  
  // Reset the array with sorted values in-place
  for (int i = 0; i < size; i++) {
    if (i < zeroes_count) {
      arr[i] = 0;
    } else {
      arr[i] = 1;
    }
  }
  
  // No return statement needed as we're modifying the array in-place
}

int main() {
  // Input array
  int input_array[] = {1, 0, 1, 1, 0, 1, 0, 0};
  int size = sizeof(input_array) / sizeof(input_array[0]);

  printf("Input array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", input_array[i]);
  }
  printf("\n");

  // Sort the array in-place
  sort_binary_array(input_array, size);

  printf("Sorted array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", input_array[i]);
  }
  printf("\n");

  return 0;
}


#include <iostream>
#include <vector>

using namespace std;

void sortBinaryArray(vector<int>& arr) {
  // Initialize counters for zeroes and ones
  int zeroesCount = 0;
  int onesCount = 0;
  
  // Count zeroes and ones in the array
  for (int num : arr) {
    if (num == 0) {
      zeroesCount++;
    } else {
      onesCount++;
    }
  }
  
  // Reset the array with sorted values in-place
  for (int i = 0; i < arr.size(); i++) {
    if (i < zeroesCount) {
      arr[i] = 0;
    } else {
      arr[i] = 1;
    }
  }
  
  // No return statement needed as we're modifying the array in-place
}

int main() {
  // Input array
  vector<int> inputArray = {1, 0, 1, 1, 0, 1, 0, 0};

  cout << "Input array: ";
  for (int num : inputArray) {
    cout << num << " ";
  }
  cout << endl;

  // Sort the array in-place
  sortBinaryArray(inputArray);

  cout << "Sorted array: ";
  for (int num : inputArray) {
    cout << num << " ";
  }
  cout << endl;

  return 0;
}


function sortBinaryArray(arr) {
  // Initialize counters for zeroes and ones
  let zeroesCount = 0;
  let onesCount = 0;
  
  // Count zeroes and ones in the array
  for (let num of arr) {
    if (num === 0) {
      zeroesCount++;
    } else {
      onesCount++;
    }
  }
  
  // Reset the array with sorted values in-place
  for (let i = 0; i < arr.length; i++) {
    if (i < zeroesCount) {
      arr[i] = 0;
    } else {
      arr[i] = 1;
    }
  }
  
  // No return statement needed as we're modifying the array in-place
}

// Input array
let inputArray = [1, 0, 1, 1, 0, 1, 0, 0];

console.log("Input array:", inputArray);

// Sort the array in-place
sortBinaryArray(inputArray);

console.log("Sorted array:", inputArray);


import java.util.Arrays;

public class Main {
  public static void sortBinaryArray(int[] arr) {
    // Initialize counters for zeroes and ones
    int zeroesCount = 0;
    int onesCount = 0;
    
    // Count zeroes and ones in the array
    for (int num : arr) {
      if (num == 0) {
        zeroesCount++;
      } else {
        onesCount++;
      }
    }
    
    // Reset the array with sorted values in-place
    for (int i = 0; i < arr.length; i++) {
      if (i < zeroesCount) {
        arr[i] = 0;
      } else {
        arr[i] = 1;
      }
    }
    
    // No return statement needed as we're modifying the array in-place
  }

  public static void main(String[] args) {
    // Input array
    int[] inputArray = {1, 0, 1, 1, 0, 1, 0, 0};

    System.out.println("Input array: " + Arrays.toString(inputArray));

    // Sort the array in-place
    sortBinaryArray(inputArray);

    System.out.println("Sorted array: " + Arrays.toString(inputArray));
  }
}

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 0s, and red balls represent 1s. 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).
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 rightpointer to the left until it finds a 0 or meets the ’left’ pointer.
If the left pointer is still less than the rightpointer:
- Swap the elements at the left and right positions.
- Increment the left pointer.
- Decrement the right pointer.
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)


#include <stdio.h>
#include <stdlib.h>

void sort_binary_array(int* arr, int size) {
  // Initialize two pointers
  int left = 0;  // Left pointer starts at the beginning of the array
  int right = size - 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 && arr[left] == 0) {
      left++;
    }

    // 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 && arr[right] == 1) {
      right--;
    }

    // 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) {
      int temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
      left++;
      right--;
    }
  }
}

int main() {
  // Input array
  int input_array[] = {1, 0, 1, 1, 0, 1, 0, 0};
  int size = sizeof(input_array) / sizeof(input_array[0]);

  printf("Input array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", input_array[i]);
  }
  printf("\n");

  // Sort the array in-place
  sort_binary_array(input_array, size);

  printf("Sorted array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", input_array[i]);
  }
  printf("\n");

  return 0;
}


#include <iostream>
#include <vector>

using namespace std;

void sortBinaryArray(vector<int>& arr) {
  // Initialize two pointers
  int left = 0;  // Left pointer starts at the beginning of the array
  int right = arr.size() - 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 && arr[left] == 0) {
      left++;
    }

    // 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 && arr[right] == 1) {
      right--;
    }

    // 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) {
      swap(arr[left], arr[right]);
      left++;
      right--;
    }
  }
}

int main() {
  // Input array
  vector<int> inputArray = {1, 0, 1, 1, 0, 1, 0, 0};

  cout << "Input array: ";
  for (int num : inputArray) {
    cout << num << " ";
  }
  cout << endl;

  // Sort the array in-place
  sortBinaryArray(inputArray);

  cout << "Sorted array: ";
  for (int num : inputArray) {
    cout << num << " ";
  }
  cout << endl;

  return 0;
}


function sortBinaryArray(arr) {
  // Initialize two pointers
  let left = 0;  // Left pointer starts at the beginning of the array
  let right = arr.length - 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 && arr[left] === 0) {
      left++;
    }

    // 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 && arr[right] === 1) {
      right--;
    }

    // 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++;
      right--;
    }
  }
}

// Input array
const inputArray = [1, 0, 1, 1, 0, 1, 0, 0];

console.log("Input array:", inputArray);

// Sort the array in-place
sortBinaryArray(inputArray);

console.log("Sorted array:", inputArray);


import java.util.Arrays;

public class Main {
  public static void sortBinaryArray(int[] arr) {
    // Initialize two pointers
    int left = 0;  // Left pointer starts at the beginning of the array
    int right = arr.length - 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 && arr[left] == 0) {
        left++;
      }

      // 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 && arr[right] == 1) {
        right--;
      }

      // 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) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
      }
    }
  }

  public static void main(String[] args) {
    // Input array
    int[] inputArray = {1, 0, 1, 1, 0, 1, 0, 0};

    System.out.println("Input array: " + Arrays.toString(inputArray));

    // Sort the array in-place
    sortBinaryArray(inputArray);

    System.out.println("Sorted array: " + Arrays.toString(inputArray));
  }
}

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.