Dutch national flag problem

"Dutch national flag" redirects here. For the flag, see Flag of the Kingdom of the Netherlands.

The Dutch national flag problem is a famous computer science related programming problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colours : Red, White and Blue. Given balls of these three colours arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of same colour are together and their collective colour groups are in the correct order.

The array case

This problem can also be viewed in terms of rearranging elements of an array. Suppose each of the possible elements could be classified into exactly one of three categories (bottom, middle, and top). For example, if all elements are in 0..1, the bottom could be defined as elements in 0..0.1, the middle as 0.1..0.3 not including 0.3 and the top as 0.3 and greater. (The choice of these values illustrates that the categories need not be equal ranges). The problem is then to produce an array such that all "bottom" elements come before (have an index less than the index of) all "middle" elements, which come before all "top" elements. And to do this sorting without later moving any element after placing it in the array.

One algorithm is to have the top group grow down from the top of the array, the bottom group grow up from the bottom, and keep the middle group just above the bottom. The algorithm stores the locations just below the top group, just above the bottom, and just above the middle in three indexes. At each step, examine the element just above the middle. If it belongs to the top group, swap it with the element just below the top. If it belongs in the bottom, swap it with the element just above the bottom. If it is in the middle, leave it. Update the appropriate index. Complexity is Θ(n) moves and examinations.

Using this algorithm in quicksort to partition elements, with the middle group being elements equal to the pivot, lets quicksort avoid "resorting" elements that equal the pivot.

Here is an example in (C++):

void threeWayPartition(int data[], int size, int low, int high) {
  int p = -1;
  int q = size;
  for (int i = 0; i < q;) {
    if (data[i] < low) {
      swap(data[i], data[++p]);
      ++i;
    } else if (data[i] >= high) {
      swap(data[i], data[--q]);
    } else {
      ++i;
    }
  }
}

Example in java (Java):

import java.util.*;
public class DutchFlag {
 
    public static void main(String[] args) {
        //Consider a case where the input numbers are not known prior.
        //so copy the array to another one, sort it to find the various numbers
        //set low to the lowest of the three numbers and high to highest of them
        //now use these pointers and to sort the original array   
        int array[] = {9,11,8,11,9,8,1};
        int size = array.length;
        int arrayCopy[] = array;
        Arrays.sort(arrayCopy);
        int low = arrayCopy[0];
        int high = arrayCopy[size-1];
        int p = 0, q= size;
        for(int i=0; i<size; i++) {
          if(array[i]==low){
                int[] num = swap(array[i],array[p]);
                array[i] = num[1];
                array[p] = num[0];
                p++;
                //i++;
            }
            else if(array[i]==high){
                 int[] num = swap(array[i], array[q-1]);
                array[i]=num[1];
                array[q-1]=num[0];
                q--;
            }
        }    
        System.out.println("The array after sort " + Arrays.toString(array));
    }
 
    public static int[] swap(int num1, int num2){
        num1 = num1 + num2;
        num2 = num1 - num2;
        num1 = num1 - num2;
        int[] num = {num1, num2};
        return num;
    }
 
 }

See also

• American flag sort

External links

• Paul E. Black, Dutch national flag at the NIST Dictionary of Algorithms and Data Structures.
• Explanation and example execution of basic algorithm
• C implementation of Dutch national flag problem with Two and Three Colour