Dutch national flag problem
Encyclopedia
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
related programming problem proposed by Edsger Dijkstra
Edsger Dijkstra
Edsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...
. The flag of the Netherlands
Flag of the Netherlands
The flag of the Netherlands is a horizontal tricolour of red, white, and blue. Since 1937, the flag has officially been the national flag of the Netherlands and of the Kingdom of the Netherlands.-Description:...
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
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
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
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
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++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
:
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
Java is an island of Indonesia. With a population of 135 million , it is the world's most populous island, and one of the most densely populated regions in the world. It is home to 60% of Indonesia's population. The Indonesian capital city, Jakarta, is in west 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
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;
}
}