基数ソート(きすうソート、英: 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進の基数ソートができる。 負の値を含む一般の整数の表現の場合(符号付数値表現を参照)、それぞれの表現毎の性質に応じて多少の注意が必要だが、基本的な所は同様におこなうことができる。 浮動小数点形式では、 任意の浮動小数点形式の場合は、 などの方策がある。 コンピュータ以外での応用に、周辺部に穴の開いた紙カードの、穴から外側の部分の紙を情報に応じて切り欠いたもの(パンチカード#ハンドソートパンチカード)のソート方法というものがある。歴史的な順序としてはこれのほうが(従って基数ソートというアイディアそのものも)、電子式のコンピュータが誕生するより古くからある。穴の場所に串を通し持ち上げると、その穴のところを切り欠いたカードが残り、切り欠いてないカードが選び出される。そうして選び出したカードを片側に寄せる。二進法の下の桁からこの操作を繰り返すと、基数ソートになる。
前提条件
アルゴリズム
入力の数列は、いくつかのキーに分類する。例えば、3桁の数字であれば、1の位・10の位・100の位に分けて分類する。
それぞれのキーについて、下位のキーからソートする。この際、値の範囲が有限であることからバケットソートが効率的である[2]。(ここで、O(n)でないソートアルゴリズムを用いると、全体の計算時間が O(nk)でなくなることに注意。また、安定なソートでなければならない。)
応用
近年ではほぼ全てである標準規格のIEEE 754形式では、float a, b が与えられたとき、a>b>0なら*(int*)&a>*(int*)&bとなるため、指数部と仮数部に分ける必要も、整数に近似する必要もない。 ⇒http://codercorner.com/RadixSortRevisited.htm を参照
適当なファクターを乗じて整数に近似して基数ソートを適用した後、元の値をバブルソート等で並び替える
内部表現を指数部・仮数部に分け、指数部を仮数部の上位キーとして基数ソートを行う(数値の内部表現の形式に依存する)
脚注[脚注の使い方]^ ソート対象が全順序であること以上のことを要求しないのが「比較によるソート」で、それに対し、何らかの位取り記数法で表現可能であることといったような、それ以上の要求があるものを「比較によらないソート」という。
^ a b 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、293-294頁。.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation.cs-ja1 q,.mw-parser-output .citation.cs-ja2 q{quotes:"「""」""『""』"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}ISBN 4-87408-414-1。
外部リンク
⇒基数ソートコード
表
話
編
歴
ソート
理論
計算複雑性理論
ランダウの記号
全順序
リスト
安定性
ソーティングネットワーク