カウント済み
移動
カウンター

  • カウント中
  • 移動済み
  • 確定

計数ソートの詳細

計数ソート

計数ソートは、値が狭い範囲の整数のときに使えます。取りうる値ごとにカウンターを1つ用意し、各値の出現回数を数え、そのカウントから各値の正確な位置がわかります。リストを読むにつれてカウンターが増え、各値が自分の区間に移るたびにまた減っていく様子を、1回ずつ見てみましょう。 「再生」で並べ替えを見るか、「ステップ」と「戻る」で移動を1回ずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。リストとバッファの行の間の帯には、値ごとにカウンターが1つあります。タイルには数えた値の数、移動回数、カウンターの数が表示されます。棒の数や初期の並びを選ぶか、数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. 棒の数と初期の並びを選ぶか、整数を自分で入力します。重複が多いリストも試してみましょう。
  2. 「再生」を押すか、「ステップ」と「戻る」で値を1つずつ動かします。ステップスライダーをドラッグすると、並べ替えの好きな位置に移動できます。
  3. カウンターに注目:リストを読む間は増え、各値を置くたびに減っていきます。

計数ソートのしくみ

最小値から最大値までのすべての値にカウンターを用意します。リストを1回読み、見つけた値のカウンターに1を足します。次に最小値からカウントを足し合わせます:ある値の区間は、それより小さい値をすべて並べた直後から始まります。最後にもう一度リストを読んで各値を自分の区間の次の空き位置へ移し、結果をコピーし戻します。

範囲が狭ければ速い

計数ソートはリストを2回読み、カウンターを1回たどるので、処理量は n + k、つまり値の数とカウンターの数の和に比例します。0〜100の試験の点数や年齢のように、狭い範囲に多くの値があるなら、どの比較ソートよりも速くなります。範囲が広いと、使われないカウンターに時間とメモリを無駄にします:1〜1,000,000に散らばった3つの値に100万個のカウンターが必要です。基数ソートが桁ごとに繰り返すのもこの手順です。

よくある質問

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

各値の出現回数を数え、カウントを足し合わせて各値の区間の開始位置を求め、各値をまっすぐ自分の区間の次の空き位置へ移します。2つの値を比較することはありません。

計数ソートはいつ使うべきですか?

値が整数(または整数に変換できる)で、最小から最大までの範囲が値の数よりそれほど大きくないときです:成績、年齢、小さなコードなど。このとき所要時間は n + k に比例します。

計数ソートは安定ですか?

はい。ここでのように、値をリストの順に自分の区間の次の空き位置へ移せば安定です。だからこそ基数ソートは各桁にこれを使えます。

数えた回数だけ各値を書き出せばいいのでは?

単なる数値ならそれで済み、しかもより簡単です。しかし実際のデータには、点数ごとの名前のようにキー以外の情報が付いていることが多く、数えたキーを書き出すだけではそれが失われます。要素そのものを移せば、付随する情報もすべて保たれます。

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

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

試してみますか?

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

エディターへ