オランダ国旗の問題

オランダのEindhoven工科大学にいたDijkstraは, 次のようなプログラミングの問題を出したといわれる.

配列a[0]からa[n-1]に青, 白, 赤いずれかがランダムにある. 1回のスキャンで青を0側, 赤をn-1側, 白を中央に揃えよ.

解法

ポインタb, x, rをb←0, x←n, r←n; と初期化し,
while b≠x do
if a[x-1]=青 then swap(a[b],a[x-1]); b←b+1;
if a[x-1]=白 then x←x-1;
if a[x-1]=赤 then swap(a[r-1],a[x-1]); x←x-1; r←r-1;
のようにループを回す.

次の図から明らかであろう.



0≤ <bの添字は青, x≤ <rの添字は白, r≤ <nの添字は赤, そしてb≤ <xの間は未処理 になっているのがこのループのinvariantである.

この問題(Dutch National Flag Problem)は, 同じ3色の国旗を持つフランス人が, オランダ人のDijkstraにプレゼンとしたといわれるが, そのフランス人の名前は失念した.