Dutch National Flag Algorithm

The Dutch national flag problem is a computational problem proposed by Edsger Dijkstra. The 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; in particular, variants of the quicksort algorithm that must be robust to 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.

Pseudocode

The following pseudocode for three-way partitioning which assumes zero-based array indexing was proposed by Dijkstra himself.It uses three indices i, j and k, maintaining the 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.

 three-way-partition(A : array of values, mid : value):
    i ← 0
    j ← 0
    k ← size of A - 1

    while i <= k:
        if A[i] < mid:
            swap A[i] and A[j]
            i ← i + 1
            j ← j + 1
        else if A[i] > mid:
            swap A[i] and A[k]
            k ← k - 1
        else:
            i ← i + 1

Leetcode problem

Loading...LeetCode