2011年5月26日 (木) 05:03時点における版編集 Luckas-bot (会話 \| 投稿記録) 384,485 回編集 m r2.7.1) (ロボットによる追加: hy:Կարգային տեսակավորում ← 古い編集		2012年1月30日 (月) 13:44時点における版編集取り消し Jkr2255 (会話 \| 投稿記録) 編集フィルター編集者、ビューロクラット、インターフェース管理者、管理者 41,479 回編集 m +ref 新しい編集 →
6行目: \|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はキーの桁数を意味する。） ==前提条件== 14行目: (1)入力の数列は、いくつかのキーに分類する。例えば、3桁の数字であれば、1の位・10の位・100の位に分けて分類する。 (2)それぞれのキーについて、下位のキーからソートする。この際、値の範囲が有限であることから[[バケットソート]]が効率的である<ref name="algo" />。（ここで、O(n)でないソートアルゴリズムを用いると、全体の計算時間が O(nk)でなくなることに注意。また、[[安定ソート\|安定]]なソートでなければならない。）たとえば、 39行目: コンピュータ以外での応用に、周辺部に穴の開いた紙カードの、穴から外側の部分の紙を情報に応じて切り欠いたもの（[[パンチカード#ハンドソート・パンチカード・システム]]）のソート方法、というものがある。穴の場所に串を通し持ち上げると、その穴のところを切り欠いたカードが残り切り欠いてないカードが選び出される。そうして選び出したカードを片側に寄せる。[[二進法]]の下の桁からこの操作を繰り返すと、基数ソートになる。 == 脚注 == {{脚注ヘルプ}} {{reflist}} ==関連項目==

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