度数ソートはソートアルゴリズムの一種。ヒストグラムソートとも。
バケットソート系のアルゴリズムであり、試験の点数の集計など上限下限が定まった統計値の処理で威力を発揮する。
ソートを始める前にまず値の度数分布を取るという異色のアルゴリズム。その発想の面白さと得意分野でのスペシャリスト振りから、時々やたらと度数ソート好きな人がいる気がする。つまりは語れるアルゴリズムである。アルゴリズムで口説ける女の子とかいませんかね。
原理
ソートの原理そのものはバケットソート。度数ソートでは配列内の統計情報から効率よくバケツを作るという点に特色がある。
- 配列を走査、各種類毎に幾つの値があるか調べて度数分布表を作る。表の大きさは値の種類の数＝バケツの数になる。例えばこんな感じ。
種類 1 2 3 4 5 6 7 8 9 10 個数 3 0 1 2 2 10 4 6 7 5 - 度数を累積度数に変換する
種類 (0) 1 2 3 4 5 6 7 8 9 10 個数 0 3 3 4 6 8 18 22 28 35 40 - 結果を格納する配列を用意する。すると、2の累積度数表は値を配列内のどこに置けばいいか示すインデックスと同一視できる。
(1: 0~2, 2: 3, 4: 4~5...)1 1 1 3 4 4 5 5 5 ...
これは種類によって移動先が決まるバケットソートの原理そのものである。 - 必要ならそれぞれのバケツ相当の内部を別のソートで入れ替える。
- ね、簡単でしょう？
一般に度数分布表を組み合わせた配列区分型のバケットソートを度数ソートといい、特にバケツ内の再ソートを伴わず単独アルゴリズムで完結するものを分布数え上げソートとか計数ソート(Counting Sort)と呼ぶ。
性能検討
ナイーブなバケットソートでは各バケツを十分な長さの配列でアロケーションするか、可変配列や連結リストをぶら下げて動的編成しなければならない。ソートの原理としては優れるバケットソートも、バケツをどう用意するかというアロケーションの問題については考慮の外である。
それに対し度数ソートでは、累積度数をインデックスに変換するという発想によって、最初から総数分の配列を用意し、それを区分けする形でバケツに使える。必ずしも結果を別の配列に移動する必要はなく、インプレイスで構成することもできるので、その気になれば度数表分のメモリオーバーヘッドだけで線形時間のソートができるという優れもの。
度数分布表作成は全要素を一度ずつ見るだけだからさほど複雑ではないし、大きさが種類の数のみで決まるため要素がいくつだろうと関係ない。例えば100点満点のテストを集計するのであれば101件分の表があればよく、人数が1万人だろうが100万人だろうがメモリオーバーヘッドは同じである。
値の範囲が最初から完全に決め打ちできるのであれば、バケットソートの本命とも言えるアルゴリズムである。
関連項目
- 1
- 0pt
