基数ソート
基数ソート（きすうソート、英: radix sort）は、「比較によらないソート」[1]のアルゴリズムの一つで、位取り記数法で表現可能な対象について、下の桁から順番にソートしてゆき、最後に最上位桁でソートすると、全体が順序通りに並ぶ、という手法である。
| クラス | ソート |
|---|---|
| データ構造 | 配列 |
| 最悪計算時間 | |
| 最悪空間計算量 |
nをデータの数、kを桁数として、計算量のオーダーはO(nk)である。また、アルゴリズム自身の性質により、素直な実装が安定ソートになる。[2]
前提条件 編集
このアルゴリズムは、データの種類が有限で、最大値・最小値がはっきりしているという仮定を置いており、全ての入力データが「3桁の整数」や「2文字のアルファベット」など決まった形式であることが分かっていなければならない。なおそれに加え、ある値のデータが必ず一つしか現れないとか、同じ値のデータは同一のものとしてしまって良い、といった場合には、もはやソートするのではなく、単純に、全体が入る大きさの配列を用意し、対応する場所に入れるだけで良いこともある（バケットソート）。
アルゴリズム 編集
基数ソートは、「複数のキーについて優先順位のあるソート」と考えることができる。すなわち、最上位桁が最も優先順位の高いキー、次いでその下の桁が2番目の優先順位のキー、3番目の桁が……、といった要領である。以下、そのような考えで「キー」という用語を使って説明する。
- 入力の数列は、いくつかのキーに分類する。例えば、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
となり、ソートが完了する。
応用 編集
コンピュータの内部では、どんなデータもバイナリであるから、それをそのまま利用して2進ないし2n進の基数ソートができる。
負の値を含む一般の整数の表現の場合（符号付数値表現を参照）、それぞれの表現毎の性質に応じて多少の注意が必要だが、基本的な所は同様におこなうことができる。
浮動小数点形式では、
- 近年ではほぼ全てである標準規格のIEEE 754形式では、float a, b が与えられたとき、a>b>0なら*(int*)&a>*(int*)&bとなるため、指数部と仮数部に分ける必要も、整数に近似する必要もない。 http://codercorner.com/RadixSortRevisited.htm を参照
任意の浮動小数点形式の場合は、
- 適当なファクターを乗じて整数に近似して基数ソートを適用した後、元の値をバブルソート等で並び替える
- 内部表現を指数部・仮数部に分け、指数部を仮数部の上位キーとして基数ソートを行う（数値の内部表現の形式に依存する）
などの方策がある。
コンピュータ以外での応用に、周辺部に穴の開いた紙カードの、穴から外側の部分の紙を情報に応じて切り欠いたもの（パンチカード#ハンドソートパンチカード）のソート方法というものがある。歴史的な順序としてはこれのほうが（従って基数ソートというアイディアそのものも）、電子式のコンピュータが誕生するより古くからある。穴の場所に串を通し持ち上げると、その穴のところを切り欠いたカードが残り、切り欠いてないカードが選び出される。そうして選び出したカードを片側に寄せる。二進法の下の桁からこの操作を繰り返すと、基数ソートになる。