基数ソート

アルゴリズム

桁数が$k$に限られた$n$個の自然数のデータが与えられているとする。すると、データは以下のアルゴリズムに従ってソートされ、その時間複雑性は$O (n)$である。

$i = 1 , \cdots , k$番目の桁数で比較してソートする。

説明

**基数ソート(Radix Sort)**は、桁数の制限があるため浮動小数点のあるデータには適用できないが、データ間の比較をせずに比較ソートアルゴリズムの限界を超えて線形時間でデータをソートできる巧妙な方法である。

例

$$ 190 \\ 812 \\ 9 \\ 77 \\ 21 \\ 413 $$ 例えば、桁数が$k=3$に限られた$n=6$個のデータは$3 \cdot 6 = 18$回でソートが完了する。まず$i=1$番目の桁でソートしてから、 $$ 19 {\color{red}0} \\ 02 {\color{red}1} \\ 81 {\color{red}2} \\ 41 {\color{red}3} \\ 07 {\color{red}7} \\ 00 {\color{red}9} $$ 次に$i=2$番目の桁でソートし、 $$ 0 {\color{red}0} 9 \\ 8 {\color{red}1} 2 \\ 4 {\color{red}1} 3 \\ 0 {\color{red}2} 1 \\ 0 {\color{red}7} 7 \\ 1 {\color{red}9} 0 $$ 最後に$i=k$番目の桁でソートすると、 $$ \color{red}{0} 0 9 \\ {\color{red}0} 21 \\ {\color{red}0} 77 \\ {\color{red}1} 90 \\ {\color{red}4} 13 \\ {\color{red}8} 12 $$ ここで注意すべき点として、$k$は桁数という定数で与えられているため$kn = O(n)$になるが、桁数がデータの数よりも多ければ当然$O(n^2)$になる。このような場合は、基数ソートを使用する理由が全くなく、比較ソートアルゴリズムを使用した方が良い。

証明

戦略：上記のプロセスを理解したなら、証明をわざわざ見る必要はない。

$0$から$9$までの数をソートする際は、それぞれの数に合わせて集めてから再度結合すれば良い。$0$なら$0$同士を集め、$1$なら$1$同士を集め、…、$9$なら$9$同士を集めた配列を作り、順番に結合すればその桁に対してはソートが完了する。桁数$k$までこれを繰り返すので、総実行回数は$k n = O(n)$になる。

■

コード

以下は基数ソートをJuliaで実装したものである。