基数ソート

基数ソート

クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	${\displaystyle O(w\cdot n)}$ここで、はキーの数、 はキーの長さです。${\displaystyle n}$${\displaystyle w}$
最悪の場合の 空間複雑度	${\displaystyle O(w+n)}$
最適	まさに正しい

コンピュータサイエンスにおいて、基数ソートは非比較 ソートアルゴリズムです。基数に応じて要素をバケットに分割して配分することで比較を回避します。有効桁数が 1 桁を超える要素の場合、このバケット分割プロセスは、前のステップの順序を維持しながら、すべての桁が処理されるまで各桁で繰り返されます。このため、基数ソートはバケット ソートやデジタル ソートとも呼ばれています。

基数ソートは、整数、単語、パンチカード、トランプ、メールなど、辞書式にソートできるデータに適用できます。

基数ソートは、1887年にハーマン・ホレリスが集計機で研究した研究にまで遡ります。^[1]基数ソートアルゴリズムは、1923年にはパンチカードをソートする方法として一般的に使用されるようになりました。 ^[2]

このソート方法のための最初のメモリ効率の良いコンピュータ アルゴリズムは、1954 年にMITのHarold H. Sewardによって開発されました。コンピュータによる基数ソートは、サイズが不明なバケットを可変に割り当てる必要があると考えられていたため、以前は非実用的であると見なされていました。Seward の革新は、線形スキャンを使用して必要なバケット サイズとオフセットを事前に決定し、補助メモリを 1 回静的に割り当てることができるようにしたことです。線形スキャンは、Seward の別のアルゴリズムであるカウンティング ソートと密接に関連しています。

現代では、基数ソートはバイナリ文字列と整数のコレクションに最も一般的に適用されています。いくつかのベンチマークでは、基数ソートは他のより汎用的なソートアルゴリズムよりも高速であることが示されており、50%から3倍高速になることもあります。^{[3] [4] [5]}

基数ソートは、最上位桁(MSD) または最下位桁(LSD)のいずれかから開始するように実装できます。たとえば、1234の場合、1 (MSD) または 4 (LSD) から開始できます。

LSD 基数ソートでは、通常、短いキーが長いキーの前に来て、同じ長さのキーが辞書式にソートされるというソート順序が使用されます。これは、[1、2、3、4、5、6、7、8、9、10、11]のような整数表現の通常の順序と一致します。LSD ソートは、一般的に安定したソートです。

MSD 基数ソートは、文字列または固定長整数表現のソートに最適です。[b, c, e, d, f, g, ba]のようなシーケンスは、 [b, ba, c, d, e, f, g]としてソートされます。 辞書式順序を使用して 10 進数の可変長整数をソートすると、1 から 10 までの数字は[1, 10, 2, 3, 4, 5, 6, 7, 8, 9]として出力されます。これは、短いキーが左揃えされ、右側に空白文字が埋め込まれて、短いキーが最も長いキーと同じ長さになっているかのように見えます。重複キーの元の順序を常に維持する必要がある場合、MSD ソートは必ずしも安定しているわけではありません。

トラバーサル順序以外に、MSD ソートと LSD ソートは可変長入力の処理方法が異なります。LSD ソートは長さでグループ化し、各グループを基数ソートしてから、サイズ順にグループを連結できます。MSD ソートでは、すべての短いキーを最大キーのサイズまで実質的に「拡張」し、それに応じてソートする必要があり、これは LSD で必要なグループ化よりも複雑になる可能性があります。

ただし、MSD ソートは、細分化と再帰に適しており、MSD ステップで作成された各バケットは、前のステップで作成された他のバケットを参照せずに、次に重要な桁を使用して基数ソートできます。最後の桁に達すると、バケットを連結するだけでソートが完了します。

入力リスト:

[170、45、75、90、2、802、2、66]

右端（最後）の桁から始めて、その桁に基づいて数字を並べ替えます。

[{17 0 , 9 0 }, { 2 , 80 2 , 2 }, {4 5 , 7 5 }, {6 6 }]

左隣の数字で並べ替え:

[{ 0 2, 8 0 2, 0 2}, { 4 5}, { 6 6}, {1 7 0, 7 5}, { 9 0}]

802 が 2 つの 2 の間に位置を維持するために、暗黙の数字0が 2 つの 2 の前に付加されていることに注意してください。

そして最後に左端の数字で:

[{ 0 0 2, 0 0 2, 0 45, 0 66, 0 75, 0 90}, { 1 70}, { 8 02}]

すべての 1 桁または 2 桁の数字の先頭に0が付加されていることに注意してください。

各項目は他の要素と比較せずにバケットに配置できるため、各ステップではデータを 1 回だけ通過するだけで済みます。

一部の基数ソートの実装では、まず各バケットに属するキーの数を数えてからキーをバケットに移動することで、バケットのスペースを割り当てます。各数字の出現回数は配列に格納されます。

カウントを使用してバケット境界を事前に決定することは常に可能ですが、一部の実装では代わりに動的メモリ割り当てを使用することを選択します。

入力リスト、先頭にゼロが付いた固定幅の数値文字列:

[170、045、075、025、002、024、802、066]

最初の数字（括弧はバケットを示します）:

[{ 0 45, 0 75, 0 25, 0 02, 0 24, 0 66}, { 1 70}, { 8 02}]

170と802はバケットに残っているものだけなのですでに完了しており、それ以上の再帰は不要であることに注意してください。

次の数字:

[{ {0 0 2}, {0 2 5, 0 2 4}, {0 4 5}, {0 6 6}, {0 7 5} }, 170, 802]

最終桁:

[ 002, { {02 4 }, {02 5 } }, 045, 066, 075 , 170, 802]

残っているのは連結だけです:

[002、024、025、045、066、075、170、802]

基数ソートは時間で動作します。ここで、はキーの数、はキーの長さです。LSD バリアントは、上で説明したように可変長キーをグループに分割するときに、「平均キー長」の下限を達成できます。 ${\displaystyle O(n\cdot w)}$${\displaystyle n}$${\displaystyle w}$${\displaystyle w}$

最適化された基数ソートは、それに適したドメインで動作する場合、非常に高速になります。^[6] 辞書式データに制限されますが、多くの実用的なアプリケーションではこれは制限ではありません。キーサイズが大きいと、パスの回数がボトルネックになり、LSD実装が妨げられる可能性があります。^[2]

バイナリ MSD 基数ソート (バイナリ クイックソートとも呼ばれる) は、入力配列を 0 ビンと 1 ビンの 2 つのビンに分割することでインプレースで実装できます。0 ビンは配列の先頭から増加し、1 ビンは配列の末尾から増加します。0 ビン境界は、配列の最初の要素の前に配置されます。1 ビン境界は、配列の最後の要素の後に配置されます。最初の配列要素の最上位ビットが調べられます。このビットが 1 の場合、最初の要素は 1 ビン境界の前の要素 (配列の最後の要素) と交換され、1 ビンは 1 境界配列インデックスを減算することで 1 要素だけ増加します。このビットが 0 の場合、最初の要素は現在の位置のままで、0 ビンは 1 要素だけ増加します。次に調べられる配列要素は、0 のビン境界の前にある要素（つまり、0 のビンにも 1 のビンにも属さない最初の要素）です。このプロセスは、0 のビンと 1 のビンが互いに到達するまで続けられます。次に、0 のビンと 1 のビンは、各配列要素の次のビットに基づいて再帰的にソートされます。再帰処理は、最下位ビットがソートに使用されるまで続きます。^{[7] [8]}符号付き2 の補数整数を処理するには、最上位ビットを逆の意味で処理し、残りのビットを符号なしで処理する必要があります。

インプレース MSD バイナリ基数ソートは、より大きな基数に拡張でき、インプレース機能も保持されます。各ビンのサイズと開始インデックスを決定するために、カウント ソートが使用されます。スワッピングは、現在の要素をそのビンに配置するために使用され、その後、ビンの境界が拡張されます。配列要素がスキャンされると、ビンはスキップされ、ビン間の要素のみが処理されます。これは、配列全体が処理され、すべての要素がそれぞれのビンに配置されるまで続きます。ビンの数は、使用される基数と同じです (たとえば、16 基数の場合は 16 ビン)。各パスは、最上位桁から開始して、1 つの桁 (たとえば、16 基数の場合は桁あたり 4 ビット) に基づきます。次に、すべての桁がソートに使用されるまで、各ビンは次の桁を使用して再帰的に処理されます。^{[9] [10]}

上の段落で説明したインプレース バイナリ基数ソートも n ビット基数ソートも安定したアルゴリズムではありません。

MSD 基数ソートは安定したアルゴリズムとして実装できますが、入力配列と同じサイズのメモリ バッファーを使用する必要があります。この追加メモリにより、入力バッファーを最初の配列要素から最後の配列要素までスキャンし、同じ順序で配列要素を宛先ビンに移動できます。したがって、等しい要素は、入力配列内と同じ順序でメモリ バッファー内に配置されます。MSD ベースのアルゴリズムでは、最初のレベルの再帰では追加メモリ バッファーを出力として使用しますが、次のレベルの再帰では入力と出力を入れ替えて、出力結果を入力バッファーにコピーし直すオーバーヘッドを回避します。各ビンは、インプレース MSD 基数ソートの場合と同様に再帰的に処理されます。最後の桁によるソートが完了したら、出力バッファーが元の入力配列であるかどうかがチェックされ、そうでない場合は 1 回のコピーが実行されます。キーサイズを桁数で割った値が偶数になるように桁数を選択すると、末尾のコピーは回避されます。^[11]

基数ソート (再帰の各レベルの最初のパスでカウント ソートを使用する2 パス メソッドなど) には、一定の大きなオーバーヘッドがあります。したがって、ビンが小さくなると、挿入ソートなどの他のソート アルゴリズムを使用する必要があります。挿入ソートの適切な実装は、小さな配列に対して高速で、安定しており、インプレースであり、基数ソートを大幅に高速化できます。

この再帰ソート アルゴリズムは、各ビンを個別にソートできるため、並列コンピューティングに特に適用できます。この場合、各ビンは次の利用可能なプロセッサに渡されます。開始時 (最上位桁) には 1 つのプロセッサが使用されます。2 番目または 3 番目の桁までに、利用可能なすべてのプロセッサが使用される可能性があります。理想的には、各サブディビジョンが完全にソートされるにつれて、使用されるプロセッサの数は徐々に少なくなります。最悪の場合、すべてのキーが互いに同一またはほぼ同一になり、その結果、並列コンピューティングを使用してキーをソートする利点はほとんどまたはまったくなくなります。

再帰の最上位レベルでは、アルゴリズムのカウントソート部分に並列処理の機会があります。カウントは高度に並列化されており、parallel_reduce パターンに適しており、メモリ帯域幅の制限に達するまで複数のコアに作業をうまく分割します。アルゴリズムのこの部分には、データに依存しない並列処理があります。ただし、後続の再帰レベルでの各ビンの処理はデータに依存します。たとえば、すべてのキーが同じ値の場合、要素を含むビンは 1 つだけであり、並列処理は利用できません。ランダム入力の場合、すべてのビンはほぼ均等に配置され、大量の並列処理の機会が利用可能になります。^[12]

より高速な並列ソートアルゴリズムも利用可能であり、例えば、Three Hungarians と Richard Cole ^{[13] [14]のアルゴリズムは最適複雑度が O(log(} n )) であり、Batcherのビットニックマージソートはアルゴリズム複雑度が O(log ² ( n ))である。これらはすべて、CREW- PRAM上の基数ソートよりもアルゴリズム時間複雑度が低い。最も高速な既知の PRAM ソートは、1991 年に David MW Powers によって記述されたものであり、 n 個のプロセッサを備えた CRCW-PRAM 上で暗黙的にパーティション分割を行うことで O(log(n)) 時間で動作できる並列化クイックソートと、同じトリックを使用して O( k )で動作する基数ソートである。ここで、 k は最大キー長である。^[15]しかし、PRAMアーキテクチャも単一のシーケンシャルプロセッサも、サイクルあたりの定数ファンアウトゲート遅延の数がO(log( n ))ずつ増加することなく拡張できるような方法で構築することは実際には不可能であるため、実質的にはBatcherのビットニックマージソートのパイプラインバージョンとO(log( n ))のPRAMソートはすべてクロックサイクルでO(log2(n))となり、Powersは、Batcherのソートは、O(nlog2(n))のキー長に依存しないソートネットワークの場合、並列クイックソートと基数ソート、またはColeのマージソートよりもゲート遅延の^定数が低くなる^ことを認めています。[ 16 ^]

基数ソートは、入力セットからツリー(または基数ツリー) を構築し、事前順序トラバーサルを実行することによっても実行できます。これは、ヒープソートとヒープデータ構造の関係に似ています。これは、特定のデータ型に役立ちます。burstsort を参照してください。

• IBM 80 シリーズ カードソーター
• その他の分布の種類
• カークパトリック・ライシュ分類
• プレフィックス合計

Wikibookアルゴリズム実装には、基数ソートに関するページがあります。

• C と Java での説明、疑似コード、実装
• JavaScriptでの LSD 基数ソートの高性能実装
• C#での LSD および MSD 基数ソートの高性能実装(GitHub のソース付き)
• MSD 基数ソートのビデオチュートリアル
• JavaScriptで実装されたRadix ソートとバブル ソート、マージ ソート、クイック ソートのデモンストレーションと比較
• IEEE 浮動小数点数の基数ソートとその実装に関する記事。

  C++ での実装による高速浮動小数点ソートと多重ヒストグラム作成

• 基数ソートの視覚化へのポインタ
• USort ライブラリは、Wayback Machineで 2011 年 8 月 7 日にアーカイブされてお​​り、ほとんどの数値 C 型 (C99) の基数ソートの調整された実装が含まれています。
• ドナルド・クヌース。『コンピュータプログラミングの芸術』第3巻：ソートと検索、第3版。Addison-Wesley、1997年。ISBN 0-201-89685-0。セクション5.2.5：分布によるソート、pp. 168–179 。 
• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第 2 版。MIT Pressおよび McGraw-Hill、2001 年。ISBN 0-262-03293-7。セクション 8.3: 基数ソート、pp. 170–173。 
• BRADSORT v1.50 ソース コード (Edward Lee 作)。BRADSORT v1.50 は、バイナリ トライ構造と循環二重リンク リストを組み合わせた基数ソート アルゴリズムです。
• Ranjan Sinha と Justin Zobel による「大規模な文字列セットの効率的なトライベース ソート」。この論文では、バケットが所定の容量を超える文字列を保持すると比喩的にサブトライにバーストするバケットのトライを作成する方法について説明しています。そのため、「バーストソート」という名前が付けられています。
• オープン データ構造 - Java 版 - セクション 11.2 - カウンティング ソートと基数ソート、Pat Morin
• オープン データ構造 - C++ 版 - セクション 11.2 - カウンティング ソートと基数ソート、Pat Morin