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

Leave a Comment / By /
  • 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.
Fig 1: array having 0 and 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.
Fig 2: Given an integer array containing 0 and 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)
Sort integer array 0 1
Fig 3: Swap elements 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.
Fig 4: Array after swapping low and high

Step 4:

  • After performing above steps we will get the array as shown in Fig 5.
Fig 5: Final array after performing sorting operation

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]

You may also like:

Classify or segregate array containing even & odd numbers in java (example)

Find a missing number in an array of distinct integers in java (example)

Majority element in integer array (Boyer Moore’s voting algorithm) in java

Reverse an integer array in java using iterative & recursive algorithm

Find maximum sum subarray in java using Kadane’s algorithm

Find missing number or element from duplicated array in java

Create or implement stack using array in java (with example)