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]