Dutch National Flag algorithm

Hello folks,

Hope you’re doing well. Today we shall discuss one of the important computer since algo called Dutch national flag. This is invented by a famous computer scientist Edsger Dijkstra.

The Dutch/Netherlands flag consists of three colors: Red, Blue, and White. The objective of this algo to arrange these colors in order (in fastest time possible) such that all the red color appear together followed by blue and while colors.

If we denote Red, Blue and While as 0, 1, 2 than if we have array as 2,0,2,1,1,0 the output should be 0,0,1,1,2,2.

Before implementing this algo, let’s go over the prior approaches to implement the color based sorting.

1. Brute:

In this approach, we care of getting the answer without worrying too much on the performance. Here we have used the in-build Sort method however you can implement custom sort as well. Per MS docs, Sort method uses heap sort for more than 16 elements and it has O(n log n) TC (Time Complexity) and for 16 elements or less, it uses insertion sort where TC can go from O(n) to O(n^2).

So in summary, the SC (Space complicity is O(1) since we’re not using any additional container object however, TC can go up to O(n^2) in the worst case.

public static void DoSortColors(int[] nums) 
        {
            Array.Sort(nums);
            //nums = Quick.QuickSort_Rec(nums, 0, nums.Length - 1);
            foreach (int item in nums) {
              Console.Write (item + " ");
            }
        }

2. Better:

In this approach, let’s try to refine the time complexity by taking 3 counter variables and then loop them parallelly to print the element.

Since there is no cascade loops, TC is O(2n) = ~O(n) whereas SC is O(1)

public static void DoSortColors2(int[] nums)
        {
            int zero = 0;
            int one = 0;
            int two = 0;

            for (int i = 0; i< nums.Length; i++) {
              if (nums[i] == 0){
                zero++;
              } else if (nums[i] == 1){
                one++;
              } else {
                two++;
              }
            }

            for (int i = 0; i< zero; i++) {
              nums[i] = 0;
            }
            for (int i = zero; i< zero+one; i++) {
              nums[i] = 1;
            }
            for (int i = zero+one; i< zero+one+two; i++) {
              nums[i] = 2;
            }

            foreach (int item in nums) {
              Console.Write (item + " ");
            }
        }

3. Optimal:

Now it’s time to introduce most optimal algo called Dutch national flag algo. This algo sorts the colors (0, 1, 2) in O(n) TC and 0(1) SC.

High level steps of algo include-

1. Have 3 pointers (low, mid, and high).
2. Initialize low and mid to 0 and high to largest index in a given array.
3. Loop until mid pointer is less/equal to high.
4. Perform series of swaps (mid with low and mid with high), until all the elements (0, 1, 2) are in order.

public static void DoSortColors3(int[] nums)
        {
            int low = 0;
            int mid = 0;
            int high = nums.Length-1;

            while (mid <=high) {
              if (nums[mid]==0) {
                (nums[low], nums[mid]) = (nums[mid], nums[low]); //swap mid wth low
                low++;
                mid++;
              } 
              else if (nums[mid]==1){
                mid++;
              }
              else{
                 (nums[high], nums[mid]) = (nums[mid], nums[high]); //swap mid wth high
                 high--;
              }
            }

            foreach (int item in nums) {
              Console.Write (item + " ");
            }
        }

Hope you’re liked the article, looking forward for your comments/ suggestions below.