What id Dutch Flag Algorithm ? || What is Dutch National Flag Algorithm ?

What is Dutch Flag Algorithm ?

The term is most commonly associated with the Dutch National Flag problem, which is a well-known algorithmic problem formulated by computer scientist Edsger W. Dijkstra. The problem involves sorting an array containing three distinct values, typically represented as colors or flags.

In this algorithm, we will have an array containing 3 integers [0,1,2] / [1,2,3] . [0,1,2] / [1,2,3] only means three distinct (different) item in the array i.e. the size of array must be greater than or equal to 3.

Assuming 0,1,2 are representing 3 distinct values of the array in sorted order.

Let number of 0's= a , number of 1's = b , number of 2's = c and size be n.

Sorted array means must look like ---

[0 to a-1] index value = 0

[a to a+b -1]index value = 1

and [a+b to n-1]index value = 2

Why do we need Dutch Flag Algorithm ?

Before understanding this, let solve this problems without Dutch National Flag Algorithm .

Let's take an example array: [2, 0, 2, 1, 1, 0]

Step 1: Counting Occurrences

• Count of 0s: 2

• Count of 1s: 2

• Count of 2s: 2

Step 2: Rewrite the Array

• First, write 2 zeros: [0, 0, ...]

• Next, write 2 ones: [0, 0, 1, 1, ...]

• Finally, write 2 twos: [0, 0, 1, 1, 2, 2]

The final sorted array is [0, 0, 1, 1, 2, 2].

Here, we are going with counting zero, one and two in one go and therefore time complexity = O(n).

and Again, iterating through the loop and reinitializing it , therefore time complexity = O(n).

So, total time required = O(n + n) = O(2n) which is ultimately O(n) and space complexity = O(1).

But, we are going through the loop twice.

Although, the above solution is O(n) still can be optimized by using DUTCH NATIONAL FLAG ALGORITHM and sort it in one go .

Approach towards Algorithm :

Step 1: Making of Three Pointer : low, mid, high

• low : 0

• mid : 0

• high : size of array -1

Step 2: We have to make our mind that we have to solve this using mid pointer only .

Step 3: Process

• Traverse the array with the mid pointer.

• If the element at mid is 0, swap it with the element at low and increment both low and mid.

• If the element at mid is 1, just set mid+=1.

• If the element at mid is 2, swap it with the element at high and set high-=1.

Code for Dutch Flag Algorithm :

Python

def dutch_national_flag(arr):
    low = 0
    mid = 0
    high = len(arr) - 1

    while mid <= high:
        if arr[mid] == 0:  #Considering 0 as smallest of distinct item
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1 #increment low by 1
            mid += 1 #increment mid by 1
        elif arr[mid] == 1: #Considering 1 as median of distinct item
            mid += 1 #increment mid by 1
        else:  # arr[mid] == 2 (which is the largest value)
            arr[high], arr[mid] = arr[mid], arr[high]
            high -= 1

C++

# include<bits/stdc++.h>
using namespace std;

vector <int> swap(vector <int> &arr, int index1, int index2)
{
    int temp = arr[index1];
    arr[index1] =arr[index2];
    arr[index2]=temp;
    return arr;
}
vector <int> dutch_flag_algorithm(vector <int> &arr)
{
    int low = 0;
    int mid = 0;
    int high = arr.size()-1;
    while(mid<high)
    {
        if(arr[mid]==2)
        {
            swap(arr,mid,high);
            high--;
        }
        if(arr[mid]==0)
        {
            swap(arr,mid,low);
            mid++;
            low++;

        }
        if(arr[mid]==1)
        {
            mid++;
        }
    }
    return arr;

}
int main()
{
    vector <int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(1);
    v.push_back(2);
    v.push_back(1);
    v.push_back(0);
    v.push_back(2);
    v.push_back(1);
    v.push_back(1);
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);
    cout<<"Actual Data : ";
    for(int i =0; i<v.size();i++)
    {
        cout<<v[i]<<' ';
    }
    cout<<endl;
    dutch_flag_algorithm(v);
    cout<<"Sorted Data : ";
    for(int i =0; i<v.size();i++)
    {
        cout<<v[i]<<' ';
    }
    cout<<endl;
}

Time Complexity and Space Complexity :

Time Complexity**: O(n)** and iteration over loop is only once.

Space Complexity**: O(1)**

I hope this blog post has been informative and insightful. If you have any questions or would like to explore more about the Algorithm, feel free to reach out or explore my other blog posts.

Twitter/X -- im_awadh_

LinkedIn -- imawadh

Instagram -- im_awadh_