「基数ソート」の版間の差分

編集の要約なし
m (+ref)
|space=<math>O(kN)</math>
|optimal=exactly correct
}}'''基数ソート'''は、[[ソート]]の[[アルゴリズム]]の一つ。計算時間は[[ランダウの記号|O]](nk)と高速で、かつ[[安定ソート]]である<ref name="algo">{{cite book | 1=和書 | title=C言語による最新アルゴリズム事典 | publisher=[[技術評論社]] | author=奥村晴彦 | authorlink=奥村晴彦 | year=1991 | pages=293-294 | isbn=4-87408-414-1}}</ref>が、O(n)の外部記憶(高速なメモリーでなくてもい)が必要。(ここで、nはデータの数、kはキーの桁数を意味する。)
 
==前提条件==
*内部表現を指数部・仮数部に分け、指数部を仮数部の上位キーとして基数ソートを行う。(実際には、数値の内部表現の形式に依存する。IEEE や IBM 浮動小数点形式では可能である。)
などの方策をとることができる。
*実は、IEEEフォーマット 場合は、float a, b ではが与えられたとき、a>b>0なら*(int*)&a>*(int*)&bってしまうのであため、指数部と仮数部に分ける必要も、整数に近似する必要もないのだ。http://codercorner.com/RadixSortRevisited.htm を参照すること
 
コンピュータ以外での応用に、周辺部に穴の開いた紙カードの、穴から外側の部分の紙を情報に応じて切り欠いたもの([[パンチカード#ハンドソート・パンチカード・システム]])のソート方法というものがある。
穴の場所に串を通し持ち上げると、その穴のところを切り欠いたカードが残り切り欠いてないカードが選び出される。そうして選び出したカードを片側に寄せる。[[二進法]]の下の桁からこの操作を繰り返すと、基数ソートになる。
 
== 脚注 ==
匿名利用者