基数ソート入門
基数(またはベース)とは、位取り方式で数を表すのに使われる桁数のことである。
2進法の場合、基数は2である(0と1の2桁しか使わない)。
10進法の場合、基数は10（0から9までの10桁ですべての数を表す）である。
位置数詞とは、簡単に言えば、数字を書くときの位置によって、その桁の重さ（値）が決まるというものです。
例えば、123という数字では、1は百を表す位置にあり、2は十を表す位置にあるため、3よりも価値が高いのです。
基数ソートは、整数、単語、メールなど多くの種類のデータを辞書式にソートするために使用できますが、主に整数や文字列のコレクションを (適切な整数のキーにマップして) ソートするために使用されます。
つまり、個々の要素を比較してコレクションをソートするのではなく、ソートするデータの本質を利用して、より速くソートするアルゴリズムです。
そのため、基数に基づいてデータをソートします。
比較ソートアルゴリズムは、最良の場合の時間複雑度がO(nlogn)であり、非比較アルゴリズムの線形実行時間（O(n+k)）より比較的悪いです。
例えば、ソートする要素の数を n とし、要素の値の許容範囲を k とする。
Counting Sort (一般的な非比較アルゴリズム) は、 k が 1..n の範囲にあるとき、その計算量は O(n+k) となる。
しかし、要素が 1..n² の範囲にある場合、複雑度は O(n²) にまで上昇し、どの比較ソートアルゴリズムよりも悪くなります。
カウントソートは、ある条件が満たされた場合のみですが、他の一般的な比較アルゴリズムよりも大幅に高速になる可能性を秘めています。
ラディックスソートのアイデアは、要素の値の範囲が要素数を大幅に超えても線形時間複雑性を維持するように、カウンティングソートをアップグレードすることである。
実際、基数ソートは本質的に計数ソートをメインサブルーチンとして使用しており、要素の値の範囲が大きくなった場合に発生する問題を克服するために、いくつかの調整が加えられている。
カウントソートアルゴリズム
Radix Sortを理解するためには、まずCounting Sortを掘り下げ、実装し、要素の値が増えることによるデメリットを観察する必要があります。
なぜ基数ソートで数え上げソートを使うのか？
カウントソートは安定した非比較ソートアルゴリズムであり、主に整数配列のソートに使用されます。
これらの特徴はすべて、Radixソートで使用するために重要です。
これらの特性を持つ限り、他のアルゴリズムをサブルーチンとして使用することも可能ですが、カウントソートが最も自然なマッチングです。
基数ソートは、入力配列の同じキー値を持つ要素の相対的な順序を維持しながら、同じ桁の値をソートする必要があります。
したがって、定義上、メインサブルーチンはある種の安定したソートアルゴリズムである必要があります。
非比較ソートアルゴリズムは一般に線形的な複雑さを持つので、基数ソートの複雑さにはあまり影響を与えません。
Pythonで数え上げソートを実装する
さて、それではPythonでCounting Sortを実装してみましょう。
I = [2, 2, 0, 6, 1, 9, 9, 7]
上記のコードを実行すると、以下のような出力が得られます。
C = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # Count array
#indices: 0 1 2 3 4 5 6 7 8 9
カウントソートの複雑さ
カウントソートの計算量は O(n+k) です。
ここで n は入力配列の要素数、 k は配列中の max 要素の値です。
この問題は，最大要素の値が配列の要素数を大幅に超える場合に発生します．kがn²に近づくと、時間計算量はO(n²)` に近づいていきます。
これはソートアルゴリズムとしては恐ろしい時間計算量です。
そこで、ラディックスソートの出番です。
基数ソートアルゴリズム
基数ソートは、要素をその明確なキー値で数えるのではなく、数字をその位置値でグループ化し、各グループでカウントソートを実行します。
開始位置は様々で、LSD（Least Significant Digits）とMSD（Most Significant Digits）が一般的であり、これらをLSD基数ソート、MSD基数ソートと呼びます。
ソートしたい入力配列を I = [2, 20, 61, 997, 1, 619] とします。
ここでは、LSD基数ソートに焦点をあてて説明します。
Pythonで基数ソートを実装する
さて、それでは最後にPythonでRadix Sortを実装してみましょう。
I = [2, 2, 0, 6, 1, 9, 9, 7] # The first element is 2
^
C = [0, 0, 1, 0, 0, 0, 0, 0, 0, 0] # We increase count of 2nd element by 1
#indices: 0 1 2 3 4 5 6 7 8 9
上のコードを実行すると、次のような出力が得られます。
C = [1, 1, 2, 0, 0, 0, 1, 1, 0, 2]
#indices: 0 1 2 3 4 5 6 7 8 9
# Element 0 has 1 occurrence
# Element 1 has 1 occurrence
# Element 2 has 2 occurrences
# Element 3 has no occurrences...
基数ソートの複雑さ
先に述べたように、ラディックスソートは線形的な時間複雑性を持つ。
もしカウントソートをメインサブルーチンとして使用する場合、基数ソートの複雑さは O(d(n+k)) となります。
これは、カウントソートを d 回実行するからであり、カウントソート自体の複雑さは O(n+k) である。
結論
基数ソートは、ある特定のケースで使用するのに最適なソートアルゴリズムです。
いくつかのベンチマークでは、基数ソートは他の汎用的なソートアルゴリズムよりも最大で3倍高速に実行できることが示されています。
入力配列のキーが短い場合や、要素の値の範囲が小さい場合に威力を発揮する。
しかし、それ以外の場合、つまり、要素の値の範囲が非常に大きく、要素の表現に桁数が多すぎる場合には、空間複雑性に劣る。
これが、たとえ線形な時間計算量を持っていても、基数ソートが他のタイプのソートアルゴリズムほど広く使われない主な理由です。