# Dutch national flag problem > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Dutch_national_flag_problem > Markdown URL: https://mediated.wiki/source/Dutch_national_flag_problem.md > Source: https://en.wikipedia.org/wiki/Dutch_national_flag_problem > Source revision: 1237943047 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) Computational problem about sorting This article needs more citations. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Dutch national flag problem" – news · newspapers · books · scholar · JSTOR (July 2014) (Learn how and when to remove this message) The Dutch national flag The **Dutch national flag problem**[1] is a [computational problem](/source/Computational_problem) proposed by [Edsger Dijkstra](/source/Edsger_Dijkstra).[2] The [flag of the Netherlands](/source/Flag_of_the_Netherlands) consists of three colors: red, white, and blue. Given balls of these three colors arranged randomly in a line (it does not matter how many balls there are), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order. The solution to this problem is of interest for designing [sorting algorithms](/source/Sorting_algorithm); in particular, variants of the [quicksort](/source/Quicksort) algorithm that must be [robust to repeated elements](/source/Quicksort#Repeated_elements) may use a three-way partitioning function that groups items less than a given key (red), equal to the key (white) and greater than the key (blue). Several solutions exist that have varying performance characteristics, tailored to sorting arrays with either small or large numbers of repeated elements.[3] ## The array case This problem can also be viewed in terms of rearranging elements of an [array](/source/Array_data_structure). Suppose each of the possible elements could be classified into exactly one of three categories (bottom, middle, and top). For example, if all the elements are in 0 ... 1, the bottom could be defined as elements in 0 ... 0.25 (not including 0.25), the middle as 0.25 ... 0.5 (not including 0.5) and the top as 0.5 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. One [algorithm](/source/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 indexes three locations, the bottom of the top group, the top of the bottom group, and the top of the middle group. Elements that are yet to be sorted fall between the middle and the top group.[4] 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.[1] ### Pseudocode The following [pseudocode](/source/Pseudocode) for three-way partitioning which assumes zero-based array indexing was proposed by Dijkstra himself.[2] It uses three indices i, j and k, maintaining the [invariant](/source/Loop_invariant) that *i* ≤ *j* ≤ *k*. - Entries from 0 up to (but not including) i are values less than mid, - entries from i up to (but not including) j are values equal to mid, - entries from j up to (and including) k are values not yet sorted, and - entries from k + 1 to the end of the array are values greater than mid. **procedure** three-way-partition(A : array of values, mid : value): i ← 0 j ← 0 k ← **size of** A - 1 **while** j <= k: **if** A[j] < mid: **swap** A[i] and A[j] i ← i + 1 j ← j + 1 **else if** A[j] > mid: **swap** A[j] and A[k] k ← k - 1 **else**: j ← j + 1 ## See also - [American flag sort](/source/American_flag_sort) - [Flag of the Netherlands](/source/Flag_of_the_Netherlands) ## References 1. ^ [***a***](#cite_ref-monash_1-0) [***b***](#cite_ref-monash_1-1) ["Dutch National Flag problem and algorithm"](http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/). Faculty of Information Technology (Clayton), Monash University, Australia. 1998. 1. ^ [***a***](#cite_ref-:0_2-0) [***b***](#cite_ref-:0_2-1) In a chapter of his book *A Discipline of Programming* Prentice-Hall, 1976 1. **[^](#cite_ref-3)** The latter case occurs in [string](/source/String_(computer_science)) sorting with [multi-key quicksort](/source/Multi-key_quicksort). Kim, Eunsang; Park, Kunsoo (2009). "Improving multikey Quicksort for sorting strings with many equal elements". *Information Processing Letters*. **109** (9): 454–459. [doi](/source/Doi_(identifier)):[10.1016/j.ipl.2009.01.007](https://doi.org/10.1016%2Fj.ipl.2009.01.007). 1. **[^](#cite_ref-NIST_4-0)** This article incorporates [public domain material](/source/Copyright_status_of_works_by_the_federal_government_of_the_United_States) from Paul E. Black. ["Dutch national flag"](https://xlinux.nist.gov/dads/HTML/DutchNationalFlag.html). *[Dictionary of Algorithms and Data Structures](https://en.wikipedia.org/w/index.php?title=Dictionary_of_Algorithms_and_Data_Structures&action=edit&redlink=1)*. [NIST](/source/National_Institute_of_Standards_and_Technology). ## External links - [Explanation and interactive explanatory execution of the algorithm](http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/), sorting two or three colors --- Adapted from the Wikipedia article [Dutch national flag problem](https://en.wikipedia.org/wiki/Dutch_national_flag_problem) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Dutch_national_flag_problem?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.