可視化したら面白そうな気がしたのでPixiJSでお絵かきをしつつ。

問題設定

Dutch national flag problemは名前の通りオランダ国旗をもとに、Edsger Djikstraが提案した問題で、
3色しかない多数のランダムシャッフルされたボールを色で整列せよ
というものです。

ちなみにオランダ国旗は赤、白、青の順です。

アルゴリズム

同じ値を多く含む場合でもクイックソートのパフォーマンスを落とさないように使われるthree-way partitioningとほぼ同じものになります。

• 次に赤が置かれるべきインデックスを r
  
• 未調査の最小インデックスを i
  
• 次に青が置かれるべきインデックスを b
  
  

を保ったまま調べていけば良いです。未調査の部分がなくなった時、つまり i > b のときに終了します。

TypeScriptによるコードだと以下のようになります。

const enum Color {
  Red,
  White,
  Blue,
}

interface Flag {
  elements: Array<Color>;
  size: number;
  color: (i: number) => Color
  swap: (i: number, j:number) => void
}

const dnf = (flag: Flag) => {
    let r = 0;
    let i = 0;
    let b = flag.size - 1;

    while (i <= b) {
        switch (flag.color(i)) {
            case Color.Red:
                flag.swap(i, r);
                i += 1;
                r += 1;
                break;
            case Color.White:
                i += 1;
                break;
            case Color.Blue:
                flag.swap(i, b);
                b -= 1;
                break;
        }
    }
}

解析

Nあった未調査部分が1ずつ小さくなってくいくので時間計算量は \( \Theta(N) \) です。

デモ