読んだ桁
移動
パス

  • 使用中のバケット
  • 直前に移動
  • 書き戻し済み
  • 確定

基数ソートの詳細

基数ソート

基数ソートは、2つの整数を一度も比較せずに並べ替えます。リストをまず一の位で、次に十の位で、さらに百の位で並べ替え、そのたびに値を10個のバケットに移して順に書き戻します。リストの下の行でバケットが1回ずつ埋まっていく様子を見て、リストがだんだん多くの桁で並んでいくのを確かめましょう。 「再生」で並べ替えを見るか、「ステップ」と「戻る」で移動を1回ずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。リストの下の行には、0〜9のバケットが横に並んでいます。タイルには読んだ桁数、移動回数、パス数が表示されます。棒の数や初期の並びを選ぶか、999までの数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. 棒の数と初期の並びを選ぶか、999までの整数を自分で入力して百の位のパスを見てみましょう。
  2. 「再生」を押すか、「ステップ」と「戻る」で値を1つずつ動かします。ステップスライダーをドラッグすると、並べ替えの好きな位置に移動できます。
  3. 各パスを見てみましょう:桁を数え、すべての値をバケットに移し、バケットを書き戻します。

基数ソートの仕組み

各数値の最後の桁だけを見て、それでリストを並べ替えます。来た順序を保ったまま、各数値を0〜9の10個のバケットのどれかに入れ、バケットを順番に書き戻します。十の位、百の位でも同じことをします。各パスは同じ数字を持つ数値の順序を保つので、それらの間の順序は前のパスで決まったままになり、最後のパスの後にはリスト全体が整列します。

比較は一切なし

比較ソートは、どんな工夫をしても、最悪の場合に少なくとも約 n log₂ n 回の比較が必要です。基数ソートは代わりに桁を読むことでこの限界を回避します。各パスですべての値の1桁を読み、すべての値を2回移動するので、d桁ならdパスで、作業量は n · d に比例して増えます。短いキーの長いリストではこれが効きます。999以下の数値100万個なら3パスで済みますが、比較ソートでは約2000万回の比較が必要です。その代わり、数字や文字でできたキーにしか使えず、バケット用の領域も必要です。

よくある質問

基数ソートはどう動くのですか?

数値を最後の桁で並べ替え、次にその前の桁で、というように最初の桁まで進めます。各パスではその桁で数値を順序を保ったまま10個のバケットに入れ、バケットを書き戻します。最上位桁のパスが終わるとリストは整列します。

なぜ最後の桁から始めるのですか?

各パスが安定だからです。同じ数字を持つ数値は、前のパスで決まった順序を保ちます。そのため最初の桁で行う最後のパスが順序を決め、同じ場合はすでに並べた桁で決まります。これをLSD(最下位桁)基数ソートと呼びます。

基数ソートはクイックソートより速いですか?

短いキーがたくさんある場合は速くなりえます。作業量は値の数×桁数に比例し、n log n がかかりません。値が少ない場合、キーがとても長い場合、数字でできていないデータの場合は、ふつうクイックソートやマージソートの方が速くて簡単です。

計数ソートとはどんな関係ですか?

基数ソートの各パスは、1つの桁での計数ソートです。各数字を持つ値の数を数え、各バケットの開始位置を求め、値を順にそこへ移します。

入力した数値はどこかに送信されますか?

いいえ。並べ替えはブラウザ内で実行され、前回の設定はこのブラウザのローカルストレージに保存されます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ