基数ソート

基数ソート

クラス	ソート
データ構造	配列
最悪計算時間	$O(kN)$
最悪空間計算量	$O(kN)$

基数ソート（きすうソート、英: radix sort）は、ソートのアルゴリズムの一つ。計算時間は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 を参照。

コンピュータ以外での応用に、周辺部に穴の開いた紙カードの、穴から外側の部分の紙を情報に応じて切り欠いたもの（パンチカード#ハンドソートパンチカード）のソート方法というものがある。歴史的な順序としてはこれのほうが（従って基数ソートというアイディアそのものも）、電子式のコンピュータが誕生するより古くからある。穴の場所に串を通し持ち上げると、その穴のところを切り欠いたカードが残り、切り欠いてないカードが選び出される。そうして選び出したカードを片側に寄せる。二進法の下の桁からこの操作を繰り返すと、基数ソートになる。

関連項目

• バケットソート

外部リンク

• 基数ソートコード