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]