Trusted answers to developer questions

The Dutch national flag problem in C++

Get Started With Data Science

Learn the fundamentals of Data Science with this free course. Future-proof your career by adding Data Science skills to your toolkit — or prepare to land a job in AI, Machine Learning, or Data Analysis.

The Dutch national flag (DNF) problem is one of the most popular programming problems proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors: white, red, and blue. The task is to randomly arrange balls of white, red, and blue such that balls of the same color are placed together.

Consider this problem on an array; the task is to sort arrays of 0, 1, and 2 in linear time without any extra space. Since the array is only traversed once, the time complexity of the algorithm given below is O(n).

Note: this algorithm can be implemented on an array that has three unique elements.

svg viewer

The following illustration shows the algorithm in action:

1 of 11

Code

In the code below, three indexes are used (i.e., low, high, mid) to sort the input array – swapping is done according to the above illustration.

// C++ program to sort an array
#include<bits/stdc++.h>
using namespace std;
// Function to sort the input array,
// the array is assumed
// to have values in {0, 1, 2}
void DNFS(int arr[], int arr_size)
{
int low = 0;
int high = arr_size - 1;
int mid = 0;
// Iterate till all the elements
// are sorted
while (mid <= high)
{
switch (arr[mid])
{
// mid is 0
case 0:
swap(arr[low++], arr[mid++]);
break;
// mid is 1 .
case 1:
mid++;
break;
// mid is 2
case 2:
swap(arr[mid], arr[high--]);
break;
}
}
}
// Function to print array arr[]
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[] = {0,0,1,2,0,1,2};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Array before running the algorithm: ";
printArray(arr, n);
DNFS(arr, n);
cout << "\nArray after DNFS algorithm: ";
printArray(arr, n);
return 0;
}

RELATED TAGS

c++
dutch flag problem
python
java
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?