Dutch National Flag Algorithm: The Dutch National Algorithm is a sorting algorithm primarily used for sorting an array consisting of three variables: 0, 1 and 2. The algorithm was first put forward by Edsger Dijkstra. The problem was inspired by the flag of the Netherlands, which consisted of three colours: Red, Blue and white. The main objective is to group each colour together.Â
The problem states that the Netherlands flag colour consists of three colors, Red, Blue and White. The objective is to arrange all these colors together. Hence, Red color together, blue together, and white color together. Consider the representation given below.
Read the complete post to understand the Dutch national flag algorithm better. The article covers the implementation, code and important highlights of the algorithm.
What is the Dutch National Flag Algorithm?
The Dutch National flag Algorithm is also known as a three way partitioning algorithm. It helps to partition an array which consists of three distinctÂ
values. The objective of this algorithm is to arrange these data meaningfully. This algorithm is frequently used for sorting an array consisting of 0s, 1s and 2s together.Â
All the 0s are kept together, 1s are kept together, followed by 2s. It is an efficient algorithm having a time complexity of O(n), and no extra space is used to implement this algorithm. Let us learn about the Dutch National Flag algorithm by taking an example below.
Learn Data Structure with PW Skills
We are providing students with the most affordable and well-packed informative computer science courses. Data structure is a very important concept required for various software developer roles. Our C++ with DSA Course consists of every important element to make you job ready.Â
The course will guide you with placement assistance, resume preparation, 1:1 doubt sessions, and lectures by industry level experts from top organizations. Hurry and join our course to avail splendid offers.
Dutch National Flag Algorithm
The table consists of the Dutch National Flag Algorithm or pseudocode, with complete steps. Learn below.
|
Dutch National Flag Algorithm |
|
Dutch National Flag Algorithm to Sort an Array of 0s, 1s and 2sÂ
Let us consider an array consisting of three distinct values, 0, 1 and 2. Now our task is to organise the array so that the output array consists of all the 0s arranged on the leftmost side, 1s arranged in the middle and 2s arranged on the rightmost side. Consider an array of size n = 7, having three values from 0 to 2.Â
Input: { 1, 2, 2, 0, 1, 2, 0 }
Output: { 0, 0, 1, 1, 2, 2, 2}
Check that the above output array is arranged in the desired manner. Let us implement the above with the help of the Dutch National Flag Algorithm. The Dutch National flag Algorithm gives the optimized solution for the above problem. The time complexity for this problem is O( N ), where N is the size of an array. Also, this solution is an in-place algorithm, hence taking no extra space in implementation. The space complexity of the Dutch National Flag Algorithm is O (1).Â
Also Read: What is kruskal algorithm
Steps To Implement Dutch National Flag Algorithm For An Array of 0s, 1s and 2s
Now, follow the steps given here to learn how to implement the Dutch National Flag Algorithm.
array [ ] = { 1, 2, 2, 0, 1, 2, 0 }
Now, let low = 0, mid = 0, and high = 6
So, our array will initially have low, mid, and high values.
Our array contains 0-based indexing, so the indexing will start from 0 to 6 for our array.
Let us follow the steps to use the Dutch National flag Algorithm to sort the array containing three distinct values.
- We will divide our array into three parts as follows: our arr[ 0… low-1] will contain 0. It is the extreme left part of our output array.
- Now our arr [ low……mid-1] will contain 1.
- Also, our array, arr [ high+1…n-1] will contain 2. It is the extreme right part of our array. Also, n-1 here stands for the size of our array.
- The middle part of our array is the unsorted part.Â
- First, we will run a loop until mid<= high.
- Now, we will adjust our pointers based on the value at mid.
- If the value arr [mid] == 0, then we will swap our arr [low]Â value with arr [mid]. Also, we will increment our low and mid pointer by 1. Based on this rule, our array from 0 to low-1 will only contain the value 0.
- However, if the value at any index, arr [mid] == 1, we will not swap any value and only increment the mid pointer by 1. Following this rule, our values from low to mid-1 will contain only 1 as per the rules.
- Now, if arr [mid] == 2, we will swap arr [mid] with arr [high]. Also, we will decrement our high value by 1. Now, our array will consist of 2 from high+1 to size of array (n) -1.
- Now, let us apply the logic to our example array.
- On index arr[0], there is 1. So, we need to apply the last logic where arr [mid] == 1. Here, we will not swap any value.
- Only increment mid pointer by 1.
- Now, we will again check our arr[mid] == 2. Hence we will swap our arr[mid] with arr[high] and also decrement our high pointer by 1.
- Now, our arr [mid] == 0, hence, we will use the first logic and swap our arr [low] with arr [mid]. Also, we will have to increment our low and mid pointers by 1 each.
- Our arr[mid] == 2, which means we have to swap our arr[mid] value with arr[high]. Also, we will decrement our high pointer by 1 after completing the swap.
- Again, our arr[mid] == 2. Now we will use our third logic again and swap our arr[mid] with arr[high]. Also, we will decrease our high pointer by 1.
- Now, we will check again the value of arr[mid] == 1, hence we will not perform any swap. However, we will increment the mid pointer by 1.
- Our arr[mid] == 0, we will swap our arr[mid] value with the arr[low] index. Also, increment the pointer low and mid by 1.
- According to the while loop condition, our mid-pointer and high-pointer crossed each other. Hence our loop will break here.
- Our output array is now sorted with the help of the Dutch National Flag Algorithm.
- The time complexity of this algorithm is O(N), where N is the size of our given array.
- Also, this algorithm does not take any extra space, and hence the space complexity of the Dutch National Flag Algorithm is O(1).Â
The complete implementation and dry run for the Dutch National Flag algorithm is given below.
Implementation of Dutch National Flag Algorithm Python
Let us check the implementation of the Dutch National flag Algorithm using Python language.
|
Dutch National Flag Algorithm Python |
| def dutchNationalAlgo(a, arr_size):
    low = 0     high = arr_size – 1     mid = 0   # Iterate till all the elements   # are sorted     while mid <= high:   # If the element is 0         if a[mid] == 0:             a[low], a[mid] = a[mid], a[low]             low = low + 1             mid = mid + 1    # If the element is 1         elif a[mid] == 1:             mid = mid + 1         # If the element is 2         else:             a[mid], a[high] = a[high], a[mid]             high = high – 1     return a # Function to print array  def printArray(a):     for k in a:         print(k, end=’ ‘) # Main Program arr = [ 1, 2, 2, 0, 1, 2, 0] arr_size = len(arr) arr = dutchNationalAlgo(arr, arr_size) printArray(arr) |
Output
The output of the above Python implementation is given below.
| 0 | 0 | 1 | 1 | 2 | 2 | 2 |
Implementation of Dutch National Flag Algorithm using JavaÂ
Let us implement the Dutch National Flag Algorithm using Java. Most developers use this language to write their code.
|
Dutch National Flag Algorithm Python |
| import java.io.*;
class Sort {     // Sort the input array, the array is assumed to     // have values in {0, 1, 2}     static void dutchNationalAlgo(int a[], int arr_size)     {         int low = 0;         int high = arr_size – 1;         int mid = 0, temp = 0;         // Iterate till all the elements         // are sorted         while (mid <= high) {             switch (a[mid]) {                 // If the element is 0             case 0: {                 temp = a[lo];                 a[low] = a[mid];                 a[mid] = temp;                 low++;                 mid++;                 break;             }                 // If the element is 1             case 1:                 mid++;                 Break;      // If the element is 2             case 2: {                 temp = a[mid];                 a[mid] = a[high];                 a[high] = temp;                 high–;                 break;             }             }         }     }     /* Utility function to print array arr[] */     static void printArray(int arr[], int arr_size)     {         int i;         for (i = 0; i < arr_size; i++)             System.out.print(arr[i] + ” “);         System.out.println(“”);     }     /*Driver function to check for above functions*/     public static void main(String[] args)     {         int arr[] = { 1, 2, 2, 0, 1, 2, 0 };         int arr_size = arr.length;         dutchNationalAlgo(arr, arr_size);         printArray(arr, arr_size);     } } |
Output
Let us check the output of the Dutch National Flag algorithm using Java.
| 0 | 0 | 1 | 1 | 2 | 2 | 2 |
Implementation of Dutch National Flag Algorithm in C++
Let us use C++ language to implement the Dutch National Flag Algorithm below.
|
Dutch National Flag Algorithm in C++ |
| #include <bits/stdc++.h>
using namespace std; // Function to sort the input array, void dutchNationalAlgo(int a[], int arr_size) {     int low = 0;     int high = arr_size – 1;     int mid = 0;     // Run the loop until all the element get sorted     while (mid <= high) {         switch (a[mid]) {    // If the element is 0         case 0:             swap(a[lo++], a[mid++]);             break;    // If the element is 1 .         case 1:             mid++;             break;   // If the element is 2         case 2:             swap(a[mid], a[high–]);             break;         }     } } // Function to print array void printArray(int arr[], int arr_size) {     // Iterate and print every element     for (int i = 0; i < arr_size; i++)         cout << arr[i] << ” “; } // Driver Code int main() {     int arr[] = { 1, 2, 2, 0, 1, 2, 0 };     int n = sizeof(arr) / sizeof(arr[0]);     dutchNationalAlgo(arr, n);     printArray(arr, n);     return 0; } |
Output
| 0 | 0 | 1 | 1 | 2 | 2 | 2 |
For Latest Tech Related Information, Join Our Official Free Telegram Group : PW Skills Telegram Group
Dutch National Flag Algorithm FAQs
What is the Dutch National Algorithm?
The Dutch National Algorithm is also known as a three way partitioning algorithm. It helps partitioning an array, which consists of three distinctÂ
values. The objective of this algorithm is to arrange these data meaningfully.Â
Is the Dutch National Flag Algorithm stable?
No, the Dutch National Flag algorithm is not stable. The relative order of the elements inside the array may change.
Who invented the 3-way partition algorithm that solves the Dutch National Flag algorithm?
The Dutch National Algorithm algorithm was proposed by the famous computer scientist Edsger Dijkstra. The Netherlands flag consists of three colors: Red, Blue, and white. The objective was to arrange them in order such that all the red color appear together and same goes for the other two colors.
What is the Dutch National Flag Algorithm Coding Question?
The Dutch National flag algorithm objective is to arrange the three colors, namely red, blue and white, so that they all appear together. Most of the time, it is used to solve array questions consisting of three colors or integer value, such as 0s, 1s, and 2s.
