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