基数ソート
ウィキペディアから
ウィキペディアから
基数ソート(きすうソート、英: 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進の基数ソートができる。
負の値を含む一般の整数の表現の場合(符号付数値表現を参照)、それぞれの表現毎の性質に応じて多少の注意が必要だが、基本的な所は同様におこなうことができる。
浮動小数点形式では、
任意の浮動小数点形式の場合は、
などの方策がある。
コンピュータ以外での応用に、周辺部に穴の開いた紙カードの、穴から外側の部分の紙を情報に応じて切り欠いたもの(パンチカード#ハンドソートパンチカード)のソート方法というものがある。歴史的な順序としてはこれのほうが(従って基数ソートというアイディアそのものも)、電子式のコンピュータが誕生するより古くからある。穴の場所に串を通し持ち上げると、その穴のところを切り欠いたカードが残り、切り欠いてないカードが選び出される。そうして選び出したカードを片側に寄せる。二進法の下の桁からこの操作を繰り返すと、基数ソートになる。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.