Dutch national flag problem or Sort array containing 0s, 1s & 2s in java

• Given an array containing unsorted integers 0,1 & 2.
• Sort the given input array using non recursive method.

Dutch national flag (DNF) problem & its flavors

1. Dutch national flag contains three colors red, white and blue.
2. Given the Balls of three colors, Our job is to arrange these balls
   • So that balls having same color are lying together.
3. Unsorted array containing three number 0s, 1s and 2s, we would like to sort the input array
   • So that 0s, 1s and 2s will lying together.

We will address the problem with point number 3 (which will holds good for other points as well)

Algorithm: sort an integer array containing 0,1 & 2 using java

• Maintain three indexes low = 0, mid = 0 and high = array length – 1
  • low, mid and high represents 0s, 1s and 2s respectively.
• Start iterating from mid to high
  • If found 0 at mid index then swap it with low
  • If found 1 at mid index (It is at it’s right place) then its fine let us increment it.
  • If found 2 at mid index, swap it with high.
• At the end of iteration, we will get the sorted or segregated array.

Program: sort an integer array containing 0,1 & 2 using java

package org.learn.arrays;

package org.learn.arrays;

import java.util.Arrays;

public class Segregate01And2 {
	public static void main(String[] args) {
		int[] example1 = { 0, 1, 2, 1, 2, 1, 0 };
		segregateArray(example1);
		System.out.println("Example 1 segregated array is : " + Arrays.toString(example1));

		int[] example2 = { 2, 1, 2, 0, 0, 2, 1 };
		segregateArray(example2);
		System.out.println("Example 2 segregated array is : " + Arrays.toString(example2));

	}

	private static void segregateArray(int[] arr) {

		int low = 0, mid = 0;
		int high = arr.length - 1;

		while (mid <= high) {

			if (arr[mid] == 0) {
				swap(arr, low, mid);
				low++;
				mid++;

			} else if (arr[mid] == 1) {
				mid++;
			} else if (arr[mid] == 2) {

				swap(arr, mid, high);
				high--;
			}
		}
	}

	private static void swap(int[] arr, int from, int to) {
		int temp = arr[from];
		arr[from] = arr[to];
		arr[to] = temp;
	}
}

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

Example 1 segregated array is : [0, 0, 1, 1, 1, 2, 2]
Example 2 segregated array is : [0, 0, 1, 1, 2, 2, 2]