基数ソートのソースを表示

{{Infobox algorithm
|class=[[ソート]]
|image=
|data=[[配列]]
|time=<math>O(kN)</math>
|space=<math>O(kN)</math>
|optimal=exactly correct
}}
'''基数ソート'''（きすうソート、{{lang-en-short|radix sort}}）は、「比較によらない[[ソート]]」<ref>ソート対象が全順序であること以上のことを要求しないのが「比較によるソート」で、それに対し、何らかの[[位取り記数法]]で表現可能であることといったような、それ以上の要求があるものを「比較によらないソート」という。</ref>の[[アルゴリズム]]の一つで、[[位取り記数法]]で表現可能な対象について、下の桁から順番にソートしてゆき、最後に最上位桁でソートすると、全体が順序通りに並ぶ、という手法である。

nをデータの数、kを桁数として、計算量のオーダーは[[ランダウの記号|O]](nk)である。また、アルゴリズム自身の性質により、素直な実装が[[安定ソート]]になる。<ref name="algo">{{cite book | 1=和書 | title=C言語による最新アルゴリズム事典 | publisher=[[技術評論社]] | author=奥村晴彦 | authorlink=奥村晴彦 | year=1991 | pages=293-294 | isbn=4-87408-414-1}}</ref>

==前提条件==
このアルゴリズムは、データの種類が有限で、最大値・最小値がはっきりしているという仮定を置いており、全ての入力データが「3桁の整数」や「2文字のアルファベット」など決まった形式であることが分かっていなければならない。なおそれに加え、ある値のデータが必ず一つしか現れないとか、同じ値のデータは同一のものとしてしまって良い、といった場合には、もはやソートするのではなく、単純に、全体が入る大きさの配列を用意し、対応する場所に入れるだけで良いこともある（[[バケットソート]]）。

==アルゴリズム==
基数ソートは、「複数のキーについて優先順位のあるソート」と考えることができる。すなわち、最上位桁が最も優先順位の高いキー、次いでその下の桁が2番目の優先順位のキー、3番目の桁が……、といった要領である。以下、そのような考えで「キー」という用語を使って説明する。
# 入力の数列は、いくつかのキーに分類する。例えば、3桁の数字であれば、1の位・10の位・100の位に分けて分類する。
# それぞれのキーについて、下位のキーからソートする。この際、値の範囲が有限であることから[[バケットソート]]が効率的である<ref name="algo" />。（ここで、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進ないし2<sup>n</sup>進の基数ソートができる。

負の値を含む一般の整数の表現の場合（[[符号付数値表現]]を参照）、それぞれの表現毎の性質に応じて多少の注意が必要だが、基本的な所は同様におこなうことができる。

[[浮動小数点数|浮動小数点形式]]では、
*近年ではほぼ全てである標準規格の[[IEEE 754]]形式では、float a, b が与えられたとき、a>b>0なら*(int*)&a>*(int*)&bとなるため、[[指数表記|指数]]部と[[仮数]]部に分ける必要も、整数に近似する必要もない。 http://codercorner.com/RadixSortRevisited.htm を参照
任意の浮動小数点形式の場合は、
*適当なファクターを乗じて整数に近似して基数ソートを適用した後、元の値を[[バブルソート]]等で並び替える
*内部表現を指数部・仮数部に分け、指数部を仮数部の上位キーとして基数ソートを行う（数値の内部表現の形式に依存する）
などの方策がある。

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

== 脚注 ==
{{脚注ヘルプ}}
{{reflist}}

== 外部リンク ==
*[http://ja.algorithm-code.com/wiki/%E5%9F%BA%E6%95%B0%E3%82%BD%E3%83%BC%E3%83%88 基数ソートコード]

{{ソート}}
[[Category:ソート|きすうそおと]]

[[no:Sorteringsalgoritme#Radix-sortering]]