Sort an integer array containing 0 & 1 in java (example)

• Given an integer array containing 0 and 1.
• We would like to sort input array.
  • Zeros will be left end of array and one will be in right end of array.
• Suppose, we would like to sort an input array, as shown in Fig 1.

Algorithm: sort integer array containing 0 & 1 in java (example):

1. Take two indexes low and high [Shown in Fig 2]
   • low will points to lowest position of an array (index = 0)
   • high will points to highest position of an array (index = array’s length – 1)
2. Start incrementing low index till we find element value = 1
   • Stops incrementing as soon as we found 1
3. Start decrementing the high index till we find element value = 0
   • Stops decrementing as soon as we found 0
4. Now swap the values pointed by low and high index ( 1 and 0)
   • After swapping, 0 will come in left side of array and 1 will be come in right side of array
5. After performing above algorithm, whole array will be sorted in O(n) times.

Step 1:  

• Take two variables, low points zeroth index of array and high points to array’s length -1.

Step 2:

• Increments low index till we find 1 and stop there
• Decrements high index till we find 0 and stop there
• Swap values pointed by low and high
  • Or we can simply assign 0 to value at low and 1 for value at high
  • We have used swapping of variables (pointed by low & high index)

Step 3:

• After step 2, we will get the array as shown in Fig 4.
• We will repeatedly keep on perform step 2 till we get the sorted array.

Step 4:

• After performing above steps we will get the array as shown in Fig 5.

Program: sort an integer array containing 0 & 1 in java

import java.util.Arrays;

public class SortArrayHaving0And1 {
 public static void main(String[] args) {
  int[] arr = { 0, 1, 0, 1, 0, 1, 0 };
  sortArray(arr);
  System.out.println("Sorted array is:"+Arrays.toString(arr));
  
 }
 private static void sortArray(int[] arr) {
  
  int low = 0;
  int high = arr.length - 1;
  
  while(low < high) {
   //increment till we find 1
   while(arr[low] == 0 && low < high)
    low ++;
   
   //decrement till we find 0
   while(arr[high] == 1 && low < high)
    high--;
   
   if(low < high) {
    //Swap or simply put 0 or 1
    int temp = arr[low];
    arr[low] = arr[high];
    arr[high] = temp;
    low ++;
    high--;
   }
  }
  return;
 }
}

Output: sort an integer array containing 0 & 1 in java

Sorted array is : [0, 0, 0, 0, 1, 1, 1]