マルチキークイックソート

マルチキークイックソート（ 3元基数クイックソートとも呼ばれる^）[1]は、文字列をソートするためのアルゴリズムです。クイックソートと基数ソートを組み合わせたこのアルゴリズムは、 C. A. R. Hoareのクイックソートに関する重要な論文の一つで報告されているように、P. Shackletonによって最初に提案されました。^[2]^{: 14}その現代版は、1990年代半ばにJon BentleyとRobert Sedgewickによって開発されました。 ^{[3]このアルゴリズムは、多くの問題において文字列が共通の}プレフィックスを持つ傾向があるという特性を利用するように設計されています。

このアルゴリズムの用途の一つはサフィックス配列の構築であり、2004年時点では最も高速なアルゴリズムの一つであった。^[4]

説明

3元基数クイックソートアルゴリズムは、 $N個$ の文字列（へのポインタ）の配列を辞書式順序でソートします。すべての文字列の長さは $K$ と等しいと仮定します。文字列の長さが可変長の場合は、文字列内のどの要素よりも小さい要素を追加して埋め込む必要があります。^[a]このアルゴリズムの擬似コードは次のとおりです^。[b]

アルゴリズムsort(a: 文字列の配列、d: 整数)は、
    長さ(a) ≤ 1またはd ≥ Kの場合に返します。
        
    p := ピボット(a, d)
    i, j := partition(a, d, p)    (2つの変数の同時割り当てに注意してください。)
    ソート(a[0:i), d)
    ソート(a[i:j), d + 1)
    ソート(a[j:長さ(a)), d)

文字列ソートアルゴリズムの多くは、文字列内の多数のバイトを調べて、ある文字列が他の文字列より小さいか、同じか、等しいかを判断し、その後、別の文字列ペアに焦点を移しますが、マルチキークイックソートでは、配列内のすべての文字列の1バイト（バイト）のみを最初に調べますd。これは、各文字列の最初のバイトです。再帰呼び出しでは、の新しい値を使用しd、部分配列を渡します。部分配列内のすべての文字列は、先頭部分（文字の前の文字）が全く同じですd。

pivot関数は1 つの文字を返す必要があります。 Bentley と Sedgewick は、a[0][d], ..., a[length(a)−1][d]の中央値か、その範囲内のランダムな文字を選択することを提案しています。^[3]パーティション関数は、通常の3 方向クイックソートで使用される関数の変形です。つまり、a[0], ..., a[i−1]のすべてに位置dの要素がpより小さいようにa を並べ替え、a[i], ..., a[j−1] には位置 $dに$ $p が$ 含まれ、 $j$ 以降の文字列にはd番目の要素が $p$ より大きいように並べ替えます。 ( Bentley と Sedgewick が提案した元のパーティション関数は、要素が重複する場合に遅くなる可能性があります。この問題を軽減するには、オランダ国旗パーティションを使用できます。^[5] )

マルチキークイックソートの実用的な実装は、クイックソートに通常適用されるのと同じ最適化（3の中央値ピボット、小さな配列の挿入ソートへの切り替えなど）の恩恵を受けることができます^。[6]

参照

アメリカ国旗ソート – 文字列ソートに高速な別の基数ソートのバリエーション
三元探索木 - 三元基数クイックソートは、クイックソートが二分探索木と同型であるのと同様に、このデータ構造と同型である^[3]

注記

^ 文字列のメモリ内表現を変更せずにこれを行う 1 つの方法は、インデックスが範囲外の場合に -1 またはその他の小さな値を返す関数を使用して文字列にインデックスを付けることです。
^ 配列と文字列はゼロインデックスです。配列スライス a[i:j)は、 aのiからjまで（この範囲は含まない）の部分配列を生成し、コピーを伴わない定数時間の処理であると想定されます。

参考文献

^ この記事には、 Paul E. Blackのパブリックドメイン資料が組み込まれています。「multikey Quicksort」。アルゴリズムとデータ構造の辞書。NIST 。
^ ホア、CAR (1962)。「クイックソート」。計算します。 J. 5 (1): 10–16 . doi : 10.1093/comjnl/5.1.10。
^ abc Bentley, Jon; Sedgewick, Robert (1997). 文字列のソートと検索のための高速アルゴリズム(PDF) . Proc. Annual ACM-SIAM Symp. on Discrete Algorithms (SODA). ISBN 0-89871-390-0。
^ Manzini, Giovanni; Ferragina, Paolo (2004). 「軽量サフィックスアレイ構築アルゴリズムの設計」. Algorithmica . 40 : 33–50 . CiteSeerX 10.1.1.385.5959 . doi :10.1007/s00453-004-1094-1.
^ Kim, Eunsang; Park, Kunsoo (2009). 「多数の等しい要素を持つ文字列のソートにおけるマルチキークイックソートの改良」. Information Processing Letters . 109 (9): 454– 459. doi :10.1016/j.ipl.2009.01.007.
^ Bentley, Jon; Sedgewick, Robert (1998). 「Three-Way Radix Quicksortによる文字列のソート」. Dr. Dobb's Journal .

[5] 文字列のメモリ内表現を変更せずにこれを行う 1 つの方法は、インデックスが範囲外の場合に -1 またはその他の小さな値を返す関数を使用して文字列にインデックスを付けることです。

[6] 配列と文字列はゼロインデックスです。配列スライス a[i:j)は、 aのiからjまで（この範囲は含まない）の部分配列を生成し、コピーを伴わない定数時間の処理であると想定されます。

[1] この記事には、 Paul E. Blackのパブリックドメイン資料が組み込まれています。「multikey Quicksort」。アルゴリズムとデータ構造の辞書。NIST 。

[2] ホア、CAR (1962)。「クイックソート」。計算します。 J. 5 (1): 10–16 . doi : 10.1093/comjnl/5.1.10。

[soda-3] Bentley, Jon; Sedgewick, Robert (1997). 文字列のソートと検索のための高速アルゴリズム(PDF) . Proc. Annual ACM-SIAM Symp. on Discrete Algorithms (SODA). ISBN 0-89871-390-0。

[4] Manzini, Giovanni; Ferragina, Paolo (2004). 「軽量サフィックスアレイ構築アルゴリズムの設計」. Algorithmica . 40 : 33–50 . CiteSeerX 10.1.1.385.5959 . doi :10.1007/s00453-004-1094-1.

[7] Kim, Eunsang; Park, Kunsoo (2009). 「多数の等しい要素を持つ文字列のソートにおけるマルチキークイックソートの改良」. Information Processing Letters . 109 (9): 454– 459. doi :10.1016/j.ipl.2009.01.007.

[8] Bentley, Jon; Sedgewick, Robert (1998). 「Three-Way Radix Quicksortによる文字列のソート」. Dr. Dobb's Journal .