Talk:Dutch national flag problem

WTF? What is this article about? I expected to see the Dutch flag but I can't even understand how anything in this article is about just that... How about a complete rewrite to let people know what's this is actually about or maybe simply delete this page. Does anyone actually read this? 81.246.93.2 11:00, 24 March 2007 (UTC)

Yes we do. It could be more helpful I admit. Edsger Dijkstra, a famous Dutch computer software theorist mentioned the "Dutch National Flag" problem which is where the term came from. The problem was - given some pebbles of 3 different colours in a line in random order (corresponding to the tricolour of the Dutch flag), can you come up with an algorithm to sort them into 3 segments of the same colour? Edgar proposed an algorithm which does just that. Since then, the phrase "Dutch National Flag" has been associated with this problem rather than the Netherlands flag. More detail can be found here:

www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

Stephen Howe 22:20, 9 May 2007 (UTC)

Suggestion for correcting the problem discription: I have seen many versions of this problem, there are constraints on memory(O(1)) and time(O(n)) but there is no condition like "only one read and one swap operation allowed on each element". So, please confirm and rewrite the description of the problem. — Preceding unsigned comment added by 182.64.207.46 (talk) 19:34, 17 August 2011 (UTC)

Correction for the Java example: The Java example was hopelessly broken, for several reasons. First the fundamental approach presented in the problem is wrong - using Arrays.sort entirely defeats the purpose of the algorithm. If you have it in sorted order you already meet the less strict conditions of the Dutch National Flag problem. However, sorting takes O(n log n) time, so you also lose the advantage of the algorithm. The second problem is that the submitter who wrote the Java code didn't realize that you to make a deep copy of the array. The shallow copy made using int arrayCopy[] = array; just resulted in a reference to the first array. The sort sorted the underlying array and covered up the several bugs that existed in the actual algorithm. I cleaned up the code (removing the confusing and useless "swap" function, changing it to the same trick I learned on the second day of programming 101) and fixed the bugs, removed the sort (replacing it with a scan of the array for min / max elements) and confirmed with a few test cases that it appears to be working properly. Enjoy. Nd tim (talk) 05:09, 10 March 2012 (UTC)

implementation wrong due to change on 23. May 2013

I believe the change on 23. May 2013 broke the implementation, at least the C++ one: I tested it using the latest change (data[i] == low) and got an unsorted result on my test data. Using the old comparison (data[i] < low) everything works fine.

For a test program on ideone.com using the current (broken) implemention, see here; the older (working) implementation is here. — Preceding unsigned comment added by CosmoDad (talk • contribs) 19:34, 1 July 2013 (UTC)

Invariant

The current invariant is claimed to be i<=j<=k. However, the loop only terminates if j>k. This is an obvious error! j<=k+1 works, though. 81.97.161.110 (talk) 12:11, 22 April 2021 (UTC)

At the moment the invariant is given as i ≤ j. This is not wrong, but it is not characterising the algorithm either. There is a stronger invariant containing the following points:

• For all x < i, A[x] < mid.
• For all x > n, A[x] > mid.
• For all x with i ≤ x < j, A[x] == mid.
• For all x with j ≤ x ≤ n, A[x] is unknown.

From these four points also follows the correctness of the algorithm.131.123.61.0 (talk) 01:07, 7 November 2014 (UTC) Unknownbeef (talk) 04:51, 13 February 2019 (UTC)

When? Where?

No reference is given to when and where Djikstra presented this algorithm. Was it during one of Djikstra summer schools? In Marktoberdorf for instance ? --PIerre.Lescanne (talk) 12:55, 20 April 2015 (UTC)

The example was given by Dijkstra in his EWD398 document (one of the thousand or so he he created for interested colleagues; I do not know the details of the mechanism he used). The document is about sequencing of primitives in code, and the problem is an illustration. The entire document is in http://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD398.html

In his book, (Edsger W. Dijkstra: A discipline of Programming}. Prentice-Hall, 1976.) he devotes a chapter to the problem. As he says there, the method was good for his purpose, but as an algorithm it was inefficient. It is the earliest example that I am aware of a three-way partition function.

I wanted to add this information to the article, but I do not know how to edit the references section, and do not want to spend the time to learn... there needs to be a way to help me help the wikipedia. Multigenerator (talk) 05:13, 23 April 2015 (UTC)