- 使用中のバケット
- 直前に移動
- 書き戻し済み
- 確定
基数ソート
基数ソートは、2つの整数を一度も比較せずに並べ替えます。リストをまず一の位で、次に十の位で、さらに百の位で並べ替え、そのたびに値を10個のバケットに移して順に書き戻します。リストの下の行でバケットが1回ずつ埋まっていく様子を見て、リストがだんだん多くの桁で並んでいくのを確かめましょう。 「再生」で並べ替えを見るか、「ステップ」と「戻る」で移動を1回ずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。リストの下の行には、0〜9のバケットが横に並んでいます。タイルには読んだ桁数、移動回数、パス数が表示されます。棒の数や初期の並びを選ぶか、999までの数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 棒の数と初期の並びを選ぶか、999までの整数を自分で入力して百の位のパスを見てみましょう。
- 「再生」を押すか、「ステップ」と「戻る」で値を1つずつ動かします。ステップスライダーをドラッグすると、並べ替えの好きな位置に移動できます。
- 各パスを見てみましょう:桁を数え、すべての値をバケットに移し、バケットを書き戻します。
基数ソートの仕組み
各数値の最後の桁だけを見て、それでリストを並べ替えます。来た順序を保ったまま、各数値を0〜9の10個のバケットのどれかに入れ、バケットを順番に書き戻します。十の位、百の位でも同じことをします。各パスは同じ数字を持つ数値の順序を保つので、それらの間の順序は前のパスで決まったままになり、最後のパスの後にはリスト全体が整列します。
比較は一切なし
比較ソートは、どんな工夫をしても、最悪の場合に少なくとも約 n log₂ n 回の比較が必要です。基数ソートは代わりに桁を読むことでこの限界を回避します。各パスですべての値の1桁を読み、すべての値を2回移動するので、d桁ならdパスで、作業量は n · d に比例して増えます。短いキーの長いリストではこれが効きます。999以下の数値100万個なら3パスで済みますが、比較ソートでは約2000万回の比較が必要です。その代わり、数字や文字でできたキーにしか使えず、バケット用の領域も必要です。
よくある質問
基数ソートはどう動くのですか?
数値を最後の桁で並べ替え、次にその前の桁で、というように最初の桁まで進めます。各パスではその桁で数値を順序を保ったまま10個のバケットに入れ、バケットを書き戻します。最上位桁のパスが終わるとリストは整列します。
なぜ最後の桁から始めるのですか?
各パスが安定だからです。同じ数字を持つ数値は、前のパスで決まった順序を保ちます。そのため最初の桁で行う最後のパスが順序を決め、同じ場合はすでに並べた桁で決まります。これをLSD(最下位桁)基数ソートと呼びます。
基数ソートはクイックソートより速いですか?
短いキーがたくさんある場合は速くなりえます。作業量は値の数×桁数に比例し、n log n がかかりません。値が少ない場合、キーがとても長い場合、数字でできていないデータの場合は、ふつうクイックソートやマージソートの方が速くて簡単です。
計数ソートとはどんな関係ですか?
基数ソートの各パスは、1つの桁での計数ソートです。各数字を持つ値の数を数え、各バケットの開始位置を求め、値を順にそこへ移します。
入力した数値はどこかに送信されますか?
いいえ。並べ替えはブラウザ内で実行され、前回の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ