計数ソート
計数ソートは値の比較をまったく使いません。すべての値が、たとえば1〜40の整数だとわかっていれば、各値がいくつあるかを数えるだけで、そのカウントから各値の位置を割り出せます。範囲が狭ければ、これ以上ないほど速い並べ替えです。
数える
最小値と最大値を見つけ、その間のすべての値にカウンターを1つずつ用意し、すべて0から始めます。リストを最初から最後まで1回読み、見つけた値のカウンターに1を足します。これでカウンターはヒストグラムになります:1がいくつ、2がいくつ、というように。値がn個、カウンターがk個なら、これにnステップかかります。
足し合わせる
最小値に等しい値が先頭に来るので、その区間は位置1から始まります。次の値の区間はその直後から始まり、以下同様です:各区間は、それより前のすべてのカウントの合計の後から始まります。この累積の合計は累積和(プレフィックスサム)と呼ばれ、ヒストグラムを整列後のリストの地図に変えます。これにkステップかかります。
置く
リストをもう一度読み、各値を自分の区間の次の空き位置へ移します。値は現れた順に移されるので、等しい値は元の順序を保ちます:計数ソートは安定です。バッファをコピーし戻せば、リストは整列済みです。アプリでは、値が置かれるにつれて各カウンターが減っていく様子が見られます。
例
4, 1, 3, 4, 2, 1, 4 を例にとります。1〜4のカウンターは最終的に 2、1、1、3 になります。足し合わせると区間が決まります:1は位置1と2、2は位置3、3は位置4、4は位置5〜7です。値をリストの順に置くと 1, 1, 2, 3, 4, 4, 4 になります:数えた値7個、移動14回、カウンター4個、比較なしです。
いつ使うか
全体の処理量は n + k に比例します。0〜100の試験の点数が1000個ある場合のように、kがnに比べて小さいときは、およそ n log₂ n 回の比較が必要な比較ソートのどれよりも計数ソートが速くなります。範囲が広いと無駄が多く、100万まで散らばった数個の値に100万個のカウンターが必要です。基数ソートは桁ごとに1回ずつ計数ソートを行うことでこれを解決し、各パスのカウンターは10個で済みます。Harold Seward は1954年に、基数ソートとともに計数ソートを記述しました。
試してみよう
アプリを開いて「ステップ」を押してください。リストとバッファの行の間の帯に、値ごとのカウンターが表示されます。リストを読む間にカウンターが増え、カウントを足し合わせるとバッファに区間が現れ、値が置かれるにつれてカウンターが減っていく様子を見てみましょう。「重複が多い」を選ぶと大きな区間が、離れた数値を入力すると広い範囲に必要なカウンターの多さがわかります。
よくある質問
計数ソートの時間計算量は?
n個の値と取りうる値k個に対して O(n + k) で、カウンターとバッファのために O(n + k) の追加メモリが必要です。
計数ソートが常に最速ではないのはなぜですか?
コストが値の個数だけでなく、値の範囲にも左右されるからです。範囲がリストよりずっと大きいと、ほとんどのカウンターは0のままで、時間とメモリが無駄になります。
計数ソートで負の数を扱えますか?
はい。カウンターは最小値から最大値まで並ぶので、最小値を引けばカウンターの添字になります。アプリも同じ方法です。
計数ソートは安定ですか?
はい。値をリストの順に自分の区間の次の空き位置へ移す限り安定です。基数ソートはその性質に頼っています。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
計数ソートを試す