まず、実行手順に従って、Radix Sortアルゴリズムの一般的なスキームを見てみましょう。
それでは、2桁の10進数（推論の単純化のために10進数）の配列を取りましょう。これは、値の昇順でソートする必要があります。
12、10、45、29、74、32、11、47、22.27。
ソートを実行するには、補助配列を作成する必要があります（現在の記事では基数配列と呼ばれます）。 配列のサイズは10要素である必要があります。要素の数は、ソート番号の最大値と同じである必要があることに注意してください（このようなソート番号は、今後の検討から明らかになります）。 補助配列は最初は空で、次のようになります。
|
|
基数配列を埋める1を渡します。
基数配列の入力を開始します。このため、ソート配列から最初の数を取得します：12、最後の桁（2）を取得し、インデックス2の配列の基数要素に12を保存します。基数配列は次のようになります。
| Idx0
| Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
|
| 1 2 |
| Idx0
| Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
|
| 1 2 | 4 5 |
| Idx0
| Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
| 1 0 | 1 1 | 1 2、3 2、2 2 | 7 4 | 4 5 | 4 7、2 7 | 2 9 |
すべての数値が基数配列にコピーされた後、基数配列の最初の要素から開始して、それらを既に新しい配列にコピーすると、次の結果が得られます。
10,11,12,32,22,74,45,47,27,29。
ご覧のように、初期番号はまだソートされていないため、基数配列を埋める追加のパスを実行する必要があります（合計で2桁の10進数の場合、2桁のパス、3桁の3桁、4桁の4桁など）。
基数配列を満たす2を渡します。
中間のソート配列から最初の数値を取得します：10、 最後から2桁の数字（1）を取得し、インデックス10で配列の基数要素に数値10を保存します。
| Idx0
| Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
|
| 1 0 |
| Idx0
| Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
|
| 1 0、1 1 |
| Idx0
| Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
|
| 1 0、1 1、1 2 | 2 2、2 7、2 9 | 3 2 | 4 5、4 7 | 7 4 |
10,11,12,22,27,29,32,45,47,74。
次に、ソートコードがCPUで実行されるときに、実際に基数配列に書き込む方法を検討します。 基数配列を埋める数値の値をどこかに格納し、できるだけ早くこれを行う必要があることは明らかです（これはアルゴリズムの並べ替えに非常に重要です）。 基数ソートの「クラシック」実装では、基数配列自体に値を格納することが提案されています。 各要素は初期番号が書き込まれる配列でもありますが、ここではメモリ消費量が多い理由が隠されています。 どの番号をソートする必要があるかが事前にわからないという事実により、元の配列のすべての数値に対して基数配列の各要素の場所を予約する必要があります。 単純化した例では、10x10要素の量のメモリを予約する必要があります;動作中のバージョンの場合、メモリサイズは256 * 10になります。 充填の2番目のパスで、この例の基数配列のメモリを整理する図を見てみましょう。
|
| |||||||||
|
| |||||||||
|
| |||||||||
|
| |||||||||
|
| |||||||||
|
| |||||||||
|
| |||||||||
|
| 12 | 29日 | |||||||
|
| 11 | 27 | 47 | ||||||
|
| 10 | 22 | 32 | 45 | 74 |
ご覧のとおり、このようなメモリ割り当てスキームは使いすぎにつながり、スキームは冗長でコストがかかります。 メモリオーバーランを必要としない基数配列を整理する方法を見つけてみましょう。 まず、考えてみましょう：どのくらいのメモリが必要ですか？ 元の配列の要素と同じ数！ 初期番号の保存を実際に実現する方法は？ 著者はさまざまなスキームを検討しました。動的メモリ割り当て、このような基数スキームでは、配列は次のようになります（簡略化）。
| 無効* | 無効* | 無効* | 無効* | 無効* | 無効* | 無効* | 無効* | 無効* | 無効* |
2番目のスキームは、追加の配列にメモリを割り当てることであり、基数配列の1つの要素の数値はリンクリストとして格納され、リストの最初の要素のインデックスは基数配列に格納されます。
これらの方法はどちらもメモリ消費量を許容レベルまで削減できますが、実際の実装では低速を示しました。動的メモリ割り当てを使用する方法が最も遅く、リンクリストを使用する方法が高速でした。 低速の理由は、最初のケースではメモリ再割り当て機能の呼び出しにコストがかかり、2番目のケースではメモリへのランダムアクセスの待ち時間が長くなることが判明しました。
その結果、メモリをより最適に使用する3番目の方法が見つかりましたが、それを埋めた後に基数配列の追加のパスを必要とします（ただし、基数配列には少数の要素があるため、これは受け入れられます）ので、スキームは次のとおりです：ソースを格納する追加の配列を作成する番号。ただし、リンクリストの形式ではなく、形式：元の番号、基数配列内の番号のインデックス。 また、基数配列には、基数配列の各要素のソース番号の総数が格納されます。 パス2の後、これらの配列は次のようになります。
基数配列：
| Idx0
| Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
| カウント：0 | カウント：3 | カウント：3 | カウント：1 | カウント：2 | カウント：0 | カウント：0 | カウント：1 | カウント：0 | カウント：0 |
| 10.1 | 11.1 | 12.1 | 32,3 | 22.2 | 74.7 | 45.4 | 47.4 | 27,2 | 29.2 |
| Idx0
| Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
| Idxr：-1 | IdxR：0 | IdxR：3 | IdxR：6 | IdxR：7 | Idxr：-1 | Idxr：-1 | IdxR：9 | Idxr：-1 | Idxr：-1 |
そして最後に、最終的な配列に追加の配列の数値を入力します（中間配列の値を使用）：たとえば、最初の数値（10.1）の場合、コピー位置は0、4番目の数値（32.3）の場合、コピー位置は6、6番目の数値（74、 7）コピー位置は9になります。番号のコピー位置がすでに取得されている場合、結果の配列の最初の非占有要素を探しています。
結果の配列：
10,11,12,22,27,29,32,45,47,74。
ご覧のとおり、結果は正しいです。
説明されているソート方法は、その特性により、Radix Compactと呼ばれていました。元のRadixソートと比較してメモリ消費が削減されました。
次に、Radix Compactアルゴリズムの一般的なプロパティとクイックソートアルゴリズムのプロパティを比較します（32ビットの数値と基数を8ビットにソートする場合）。
| 基数コンパクト | クイックソート | |
| 計算の複雑さ
ベストケース | N *（2）+ 256 * 1 | N *ログ（N） |
| 計算の複雑さ
最悪の場合 | N *（8）+ 256 * 4 | N 2 |
| 追加メモリ | N +サイズ（基数配列） | ログ（N） |
| 超並列機能
計算 | はい | いや |
| メモリアクセス | 適度にランダム | 線形 |
| 処理の局所性
（配置に重要 CPUキャッシュ内のデータ） | 十分な | 高い |
理論的には、Radix Compactアルゴリズムには優れた特性があるため、実際に確認してみましょう。 まず、「ホームフィールド」クイックソートでのアルゴリズムの動作の結果を比較しましょう。32ビット数の配列のシングルスレッド実装で：
テストはIntel i5-3330 CPU（3000 MHz）、メモリ容量：16 GB、OS：Windows 8.0 64ビットで実施されました。 Radix Compactのソートコードは、C ++、クイックソートの実装であるstd :: sort（）で記述されています。 注：わずかに変更されたRadix Compactがテストされ、Radix Compactランタイムにはメモリ割り当て時間が含まれていません。
ご覧のとおり、クイックソートの最も有利な条件であっても、Radix Compactは最大7倍の速度でそれを上回り、小さなサイズの配列（最大100要素）でのみ失われます。 これは理解できるからです Radix Compactは小さな基数配列の追加処理を必要とします。大きな配列の場合、今回は実際には結果に影響しませんが、小さな配列の場合は重要です。 ただし、一般に、Radix Compactの結果はかなりまともです。 記事の次の部分では、GPUでの実行にアルゴリズムを適合させた結果について説明します;計算の並列化は、標準のクイックソートと比較してさらに大きなゲインをもたらすことを約束します。