オランダ国旗問題[1]は、エドガー・ダイクストラ[2]によって提唱された計算問題である。オランダの国旗は、赤、白、青の3色で構成されている。これらの3色のボールがランダムに一列に並べられている（ボールの数は問わない）と仮定し、同じ色のボールがすべて揃い、かつそれらの色のグループが正しい順序になるように並べるという問題である。
この問題の解決策は、ソートアルゴリズムの設計において重要です。特に、繰り返し要素に対して堅牢性が必要なクイックソートアルゴリズムの派生では、与えられたキーより小さい要素（赤）、キーと等しい要素（白）、キーより大きい要素（青）をグループ化する3分割関数が用いられる場合があります。繰り返し要素の数が少ない配列や多い配列のソートに適した、パフォーマンス特性の異なる複数のソリューションが存在します。[3]
配列の場合
この問題は、配列の要素の並べ替えという観点からも捉えることができます。それぞれの要素が3つのカテゴリ（下、中、上）のいずれかに分類できると仮定します。例えば、すべての要素が0 ... 1の範囲にある場合、下は0 ... 0.25（0.25は含まない）、中は0.25 ... 0.5（0.5は含まない）、上は0.5以上の範囲にある要素と定義できます。（これらの値の選択は、カテゴリが必ずしも同じ範囲である必要がないことを示しています。）問題は、すべての「下」要素がすべての「中」要素の前に来る（インデックスが「中」要素のインデックスより小さい）ような配列を作成することです。「中」要素はすべての「上」要素の前に来ます。
一つのアルゴリズムは、最上位グループを配列の上から下へ、最下位グループを下から上へ成長させ、中間グループを最下位のすぐ上に配置するというものである。このアルゴリズムは、最上位グループの下、最下位グループの上、中間グループの上の3つの位置にインデックスを付ける。まだソートされていない要素は、中間グループと最上位グループの間にある。[4]各ステップで、中間のすぐ上の要素を調べる。それが最上位グループに属する場合、それを最上位のすぐ下の要素と交換する。それが最下位グループに属する場合、それを最下位のすぐ上の要素と交換する。中間グループにある場合はそのまま残す。適切なインデックスを更新する。計算量はΘ(n)回の移動と検査である。[1]
擬似コード
ゼロベースの配列インデックスを前提とした3分割の次の疑似コードは、ダイクストラ自身によって提案されました。 [2] i、j、kの3つのインデックスを使用し、 i ≤ j ≤ kという不変条件を維持します。
- 0からiまで（iは含まない）のエントリはmid未満の値です。
- iからjまでの（ただし j を含まない）エントリはmidに等しい値です。
- jからkまでのエントリはまだソートされていない値であり、
- k + 1から配列の最後までのエントリはmidより大きい値です。
手順three-way-partition(A: 値の配列、mid: 値):
私 ← 0
j ← 0
k ← Aの大きさ- 1
j <= k
の場合: A[j] < midの
場合: A[i]とA[j]を入れ替える
私 ← 私 + 1
j ← j + 1
そうでない場合、 A[j] > mid:
A[j]とA[k]を入れ替える
k ← k - 1
それ以外：
j ← j + 1
参照
参考文献
- ^ ab 「オランダ国旗問題とアルゴリズム」モナッシュ大学情報技術学部（クレイトン）、オーストラリア。1998年。
- ^ ab 著書『プログラミングの規律』（プレンティス・ホール、1976年）の一章より
- ^ 後者のケースは、マルチキークイックソートを用いた文字列ソートで発生します。Kim , Eunsang; Park, Kunsoo (2009). 「多数の等しい要素を持つ文字列のソートにおけるマルチキークイックソートの改良」. Information Processing Letters . 109 (9): 454– 459. doi :10.1016/j.ipl.2009.01.007.
- ^
この記事には、 Paul E. Blackのパブリックドメイン資料が組み込まれています。「オランダ国旗」。アルゴリズムとデータ構造の辞書。NIST 。
外部リンク
- 2色または3色のソートアルゴリズムの説明とインタラクティブな説明実行