C++: Dutch National Flag Problem

Posted on September 1, 2017October 10, 2017 by TFE Times

Bjarne-stroustrup

The Dutch national flag is composed of three coloured bands in the order red then white and lastly blue. The problem posed by Edsger Dijkstra is:

Given a number of red, blue and white balls in random order, arrange them in the order of the colours Dutch national flag.

When the problem was first posed, Dijkstra then went on to successively refine a solution, minimising the number of swaps and the number of times the colour of a ball needed to determined and restricting the balls to end in an array, …

This task is to

Generate a randomized order of balls ensuring that they are not in the order of the Dutch national flag.
Sort the balls in a way idiomatic to your language.
Check the sorted balls are in the order of the Dutch national flag.

#include <algorithm>
#include <iostream>

// Dutch national flag problem
template <typename BidIt, typename T>
void dnf_partition(BidIt first, BidIt last, const T& low, const T& high)
{
	for (BidIt next = first; next != last; ) {
		if (*next < low) {
			std::iter_swap(first++, next++);
		} else if (!(*next < high)) {
			std::iter_swap(next, --last);
		} else {
			++next;
		}
	}
}

enum Colors { RED, WHITE, BLUE };

void print(const Colors *balls, size_t size)
{
	static const char *label[] = { "red", "white", "blue" };

	std::cout << "Balls:";
	for (size_t i = 0; i < size; ++i) {
		std::cout << ' ' << label[balls[i]];
	}
	std::cout << "\nSorted: " << std::boolalpha << std::is_sorted(balls, balls + size) << '\n';
}

int main()
{
	Colors balls[] = { RED, WHITE, BLUE, RED, WHITE, BLUE, RED, WHITE, BLUE };

	std::random_shuffle(balls, balls + 9);
	print(balls, 9);

	dnf_partition(balls, balls + 9, WHITE, BLUE);
	print(balls, 9);
}

Output:

Balls: blue white red blue red blue white red white
Sorted: false
Balls: red red red white white white blue blue blue
Sorted: true

Content is available under GNU Free Documentation License 1.2.

Related