基数ソート

基数ソートは、ソートのアルゴリズムの一つ。計算時間はO(nk)と高速だが、O(n)の外部記憶（高速なメモリーでなくても良い）が必要。（ここで、nはデータの数、kはキーの数を意味する。）

前提条件

基数ソートのアルゴリズムは、データの種類が有限で、最大値・最小値がはっきりしていることを仮定している。すべての入力データが「3桁の整数」や「2文字のアルファベット」など決まった形式であることが分かっているときに適用できる。

アルゴリズム

(1)入力の数列は、いくつかのキーに分類する。例えば、3桁の数字であれば、1の位・10の位・100の位に分けて分類する。

(2)それぞれのキーについて、下位のキーからソートする。この際、値の範囲が有限であることからバケットソートが効率的である。（ここで、O(n)でないソートアルゴリズムを用いると、全体の計算時間が O(nk)でなくなることに注意。また、安定なソートでなければならない。）

たとえば、

170, 45, 75, 90, 2, 24, 802, 66

という数列を1の位についてソートすると、

170, 90, 2, 802, 24, 45, 75, 66

となる。さらに、10の位についてソートすると、

2, 802, 24, 45, 66, 170, 75, 90

となる。最後に、100の位についてソートすると、

2, 24, 45, 66, 75, 90, 170, 802

となり、ソートが完了する。

応用

コンピュータの数値の内部表現は、通常4バイトや8バイトのビット列となっている。

これら4バイト（8バイト）の整数については、1バイトずつ（あるは4ビットずつ）のキーに分類して基数ソートを適用することが可能である。ただし、通常、最上位部に「符号ビット」を持つため、これに関して特別な扱いをする必要がある。

浮動小数点形式の数値については、

• 適当なファクターを乗じて整数に近似して基数ソートを適用した後、元の値をバブルソート等で並び替える。
• 内部表現を指数部・仮数部に分け、指数部を仮数部の上位キーとして基数ソートを行う。（実際には、数値の内部表現の形式に依存する。IEEE や IBM 浮動小数点形式では可能である。）

などの方策をとることができる。

• 実は、IEEEフォーマットのfloat a,b では、a>b>0なら*(int*)&a>*(int*)&bになってしまうのである。指数部と仮数部に分ける必要も、整数に近似する必要もないのだ。http://codercorner.com/RadixSortRevisited.htm を参照すること

関連項目

• バケットソート

外部リンク

• 基数ソートコード