1. Introduction

Sorting an array that consists of only 0’s, 1’s, and 2’s is commonly known as the Dutch National Flag Problem. The problem is inspired by the Dutch National Flag, which comprises three colors: red, white, and blue. The objective is to segregate the 0’s, 1’s, and 2’s in such a manner that all the 0’s come first, followed by all the 1’s and then the 2’s, similar to the Dutch National Flag. The catch is to solve the problem in linear time and without using any sorting function.

2. Program Steps

1. Create three pointers: low, mid, and high. Initialize low and mid at the start of the array and high at the end of the array.

2. Traverse the array using the mid pointer.

3. If the element at the mid index is 0, swap the elements at low and mid indexes, and increment both low and mid.

4. If the element at the mid index is 1, just increment the mid pointer.

5. If the element at the mid index is 2, swap the elements at mid and high indexes, and decrement the high pointer.

6. Repeat the above steps until the mid pointer crosses the high pointer.

3. Code Program

public class DutchNationalFlag {

    public static void sort(int[] arr) {
        int low = 0, mid = 0, high = arr.length - 1;

        while (mid <= high) {
            switch (arr[mid]) {
                // If the element is 0
                case 0:
                    swap(arr, low, mid);
                    low++;
                    mid++;
                    break;

                // If the element is 1
                case 1:
                    mid++;
                    break;

                // If the element is 2
                case 2:
                    swap(arr, mid, high);
                    high--;
                    break;
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 0};
        sort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Output:

0 0 0 0 0 1 1 1 1 2 2 2

4. Step By Step Explanation

1. We use three pointers low, mid, and high to traverse and modify the array simultaneously.

2. The low pointer is responsible for the position where the next 0 should be placed, the mid pointer traverses the array, and the high pointer indicates the position where the next 2 should be placed.

3. Depending on the value at the mid pointer, we make the necessary swaps to ensure that 0's come before 1's and 1's come before 2's.

4. The swap function is a utility function to swap values at two indexes in the array.

5. This approach segregates the 0's, 1's, and 2's in a single traversal, making it an optimal solution for the problem.