Well, apparently the famous programmer Dijkstra from Netherlands used the concept of the Dutch national flag as a proof for a problem . The problem was to efficiently sort N balls having the colors Red , White and Blue such that same colored balls appeared adjacent and they should be ordered.

He named this proof by Dutch National Flag since it had similar color scheme.

So if you are wondering how he solved it in-place without counting the similar colored balls then READ ON!

He knew that Red colored balls must appear at the beginning similarly the balls of blue color will be at end. So he used three pointers each of them keeping the track of different colors present. Say start for Red , mid for White and end for Blue.

He partitioned the space into 4 different sections they were ,

1. 1 to start-1 for Red colored balls.
2. start to mid-1 for blue colored balls.
3. mid to high for the unknown elements #This section was supposed to be shrunk as we came to know what was inside of it.
4. Finally , high+1 to N for Blue colored balls.

This problem is also represented in modern days as 0,1,2 sorting problem. But it can be extended to K different elements but its complexity increases w.r.t to number of different elements. SO it is not used independently but used to tweak the regular in-place divide and conquer and stable sorter THE QUICK SORT. But here I explain the independent implementation, In the next article I shall explain how Quick Sort can be tweaked to get better results on repeated similar elements using DNF.

So coming to the problem , taking an example B,B,W,W,B,B,B,B,W,R or 2, 2, 1, 1, 2 ,2 ,2 ,2 ,1,0 as the different colored balls placed in random order we need to sort them in-place meaning you can only exchange the balls, in CS do not use any new array but change in the same array.

Seeing this order we realize that B should be at the end and R should be the beginning, by doing this we also place the W at their positions by default.

Intially place start and mid pointers at 0th index that is the first ball, place the end pointer at the last index(ball).

So start traversing from left to right , the color will be inspected by the mid pointer since it is one which is unknown. If mid is pointing towards R then swap mid with start since that's where it needs to be and also increment the start and mid pointers shrinking the unknown size since the ball is placed at the right place.

If mid pointers encounters a W ball then just increment mid since it also in the right place but when mid encounters a B ball then it is in the wrong position and needs to be placed where end is pointing to , so swap end and mid balls also shrink end pointer since it is B . Important to remember here is not to shrink the mid since the swapped ball is not checked if its a W or a R ball. So check it in the next loop and place it in the right position.

This is how DUTCH NATIONAL FLAG PROBLEM was solved ! The Pseudo code for this algorithm is :

1. SET start = 0 , mid = 0 , end = last-position(The len -1 )
2. Traverse until mid is less than or equal to end i,e mid≤end
3. IF arr[mid] is 0(R) then SWAP(arr[mid], arr[low) also INCREMENT mid and start by 1.
4. ELSE IF arr[mid] is 1 then just INCREMENT mid by 1.
5. ELSE IF arr[mid] is 2 then SWAP(arr[mid], arr[end]) also DECREMENT only end by 1. Since the swapped element is unknown.
6. Return arr.

So this was an article on Dutch National Flag Problem. Please leave a clap if you enjoyed and also feel free to comment your queries!

Below is the tracing of this algorithm.

defalut : start = 0 mid = 0 end = 9

1 1 1 1 2 0 2 2 2 2 start = 0 mid = 1 end = 9

1 1 1 1 2 0 2 2 2 2 start = 0 mid = 2 end = 9

1 1 1 1 2 0 2 2 2 2 start = 0 mid = 3 end = 9

1 1 1 1 2 0 2 2 2 2 start = 0 mid = 4 end = 9

1 1 1 1 2 0 2 2 2 2 start = 0 mid = 4 end = 8

1 1 1 1 2 0 2 2 2 2 start = 0 mid = 4 end = 7

1 1 1 1 2 0 2 2 2 2 start = 0 mid = 4 end = 6

1 1 1 1 2 0 2 2 2 2 start = 0 mid = 4 end = 5

1 1 1 1 0 2 2 2 2 2 start = 0 mid = 4 end = 4

0 1 1 1 1 2 2 2 2 2 start = 1 mid = 5 end = 4

Code:

Thank You!