What is Dutch National Flag algorithm

Definition

The Dutch National Flag algorithm is an algorithm used to sort an array consisting of 0s and 1s.

Scenarios to Consider

• When an array contains 0s and 1s and you want to sort them to distinguish between the two.

• When you want to sort the elements of an array in-place without using additional memory.

Cases where it should not be used

The Dutch National Flag algorithm can only be used to sort arrays consisting of 0s and 1s. For sorting other types of elements, a different algorithm should be used.

Advantages

• It can sort an array in-place without using additional memory.

• Time complexity: O(n)

• Space complexity: O(1)

Disadvantages

• It can only be applied to arrays consisting of 0s and 1s, making it unsuitable for sorting other types of elements.

• It can only sort two types of elements (0s and 1s), so modifications are needed if other types of elements are introduced.

Implementation Steps

1. Initialize the first pointer (low) at the beginning of the array, and the second (mid) and third (high) pointers at the end of the array.

2. Repeat the following steps while the mid pointer is less than or equal to the high pointer:

   • Based on the value of arr[mid], perform the following actions:

     • If it's 0: Swap the values of arr[low] and arr[mid], and increment low and mid by 1.

     • If it's 1: Increment the mid pointer by 1.

     • If it's 2: Swap the values of arr[mid] and arr[high], and decrement high by 1.

3. Return the sorted array.

Example

The following is an example Java implementation of the Dutch National Flag algorithm:

public class DutchNationalFlagAlgorithm {
    public static void dutchNationalFlagSort(int[] nums) {
        int low = 0;  // Pointer for 0
        int mid = 0;  // Pointer for 1
        int high = nums.length - 1;  // Pointer for 2

        while (mid <= high) {
            if (nums[mid] == 0) {
                // Swap the current element with the low pointer element
                swap(nums, low, mid);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                // Move the mid pointer
                mid++;
            } else if (nums[mid] == 2) {
                // Swap the current element with the high pointer element
                swap(nums, mid, high);
                high--;
            }
        }
    }

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