Dutch National Flag Algorithm

The Dutch National Flag Algorithm, also known as the Dutch National Flag problem, is a sorting algorithm designed to segregate an array containing three distinct elements. It was proposed by Edsger Dijkstra and is named after the Dutch national flag, which has three colors: red, white, and blue. The goal of the algorithm is to rearrange the elements of the array in such a way that all elements of one type appear together.

Source

1. Initialize three pointers: low, mid, and high.

● low points to the beginning of the array.

● mid points to the current element being processed.

● high points to the end of the array.

2. Start iterating through the array while mid is less than or equal to high.

3. If the element at the mid pointer is the first type (e.g., 0), swap it with the element at the low pointer. Increment both low and mid pointers.

4. If the element at the mid pointer is the second type (e.g., 1), leave it in place and only increment the mid pointer.

5. If the element at the mid pointer is the third type (e.g., 2), swap it with the element at the high pointer. Decrement the high pointer.

6. Continue this process until mid is greater than high.

Example:

Suppose you have an array: [1, 0, 2, 1, 2, 0].

• Initially: low=0, mid=0, high=5.

The algorithm proceeds as follows:

• Swap 1 at mid with 0 at low: [0, 1, 2, 1, 2, 0], low=1, mid=1, high=5.
• Leave 1 at mid in place, increment mid: [0, 1, 2, 1, 2, 0], low=1, mid=2, high=5.
• Swap 2 at mid with 0 at high: [0, 1, 0, 1, 2, 2], low=1, mid=2, high=4.
• Swap 0 at mid with 1 at low: [0, 0, 1, 1, 2, 2], low=2, mid=3, high=4.

The array is now sorted, with all 0s, 1s, and 2s grouped together. This algorithm is efficient with a time complexity of O(n), where n is the number of elements in the array, as it sorts the array in a single pass.

import java.util.*;

public class Main {

    public static void sortArray(ArrayList<Integer> arr, int n) {
        int low = 0, mid = 0, high = n - 1; // 3 pointers

        while (mid <= high) {
            if (arr.get(mid) == 0) {
                // swapping arr[low] and arr[mid]
                int temp = arr.get(low);
                arr.set(low, arr.get(mid));
                arr.set(mid, temp);
                low++;
                mid++;
            } else if (arr.get(mid) == 1) {
                mid++;
            } else {
                // swapping arr[mid] and arr[high]
                int temp = arr.get(mid);
                arr.set(mid, arr.get(high));
                arr.set(high, temp);
                high--;
            }
        }
    }

    public static void main(String args[]) {
        int n = 6;
        ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(new Integer[] {0, 2, 1, 2, 0, 1}));
        sortArray(arr, n);
        System.out.println("After sorting:");
        for (int i = 0; i < n; i++) {
            System.out.print(arr.get(i) + " ");
        }
        System.out.println();
    }
}