6．9 度数ソート
番号 以下をクリックすると，該当箇所にジャンプします （１） ヒープ （２） 完全２分木の配列による表現 （３） ヒープソート （４） ヒープの構築 （１）度数ソートの考え方 度数ソートでは，累積度数分布表を作成し， 累積度数分布表を利用してソートを行います。 テストの点数など， 取りうる値の範囲が決まっているときに有用です。 　　 （２）度数ソートの手順 度数ソートは，次のような手順で行います。 　�@）度数分布表の作成 　　 　　各点数の学生が何人いるかを示す度数分布表を作成します。 　�A）累積分布表の作成 　　 　　その点数以下の学生が何人いるかを示す累積度数分布表を 　　　作成します。 　�B）目的配列の作成 　　　　原配列と累積度数分布表をつき合わせてソート済み配列を 　　　作成します。 （３）度数分布表の作成 このためには，値の最大値＋１のサイズの配列を用意し， 各点数をカウントします。 　　 （４）累積度数分布表の作成 この処理は，度数分布表の前の値にその位置の値を加えるだけです。 　　 （５）目的配列の作成 まず，原配列と同じサイズの配列を用意します。 そして，原配列の最後から前の方にスキャンしながら 累積度数分布と突合せます。 以下の例では，最後の値が５ですから， 累積度数分布の添え字５の要素をみると６ですから， ５点以下の学生が６人いることになります。 すなわち，５点の学生は６位となります。 したがって，目的配列の６番目（配列添え字は５）に５点を入れます。 この際，該当する累積度数分布表の値をデクリメント（−１する） しておきます。 すなわち，累積度数分布の添え字５の部分は６から５に変わります。 　　　 同様に前の値を付き合わせます。 ３点の学生は３番目（配列添え字＝２）に入ります。 　　　 同様に前の値を付き合わせます。 ５点の学生が入る位置は，以前デクリメントされていますから， ５番目に変わっていますので， 配列添え字４の位置に入ることになります。 すなわち，累積度数分布表をデクリメントしているのは， 同一の値がある場合に対応するためです。 　　　 このようにして，順次，前方向に付き合わせながら， 目的配列に入れていきます。 　　　 　　　 　　　　 ［プログラム］ 　　private void FrequencySort(ref int[] a, int max) 　　{ 　　　　int i; 　　　　int[] 度数 = new int[max+1]; 　　　　int[] temp = new int[a.Length]; 　　　　for(i=0; i<度数.Length; i++) 度数[i]=0; 　　　　for(i=0; i< a.Length; i++) 度数[a[i]]++; 　　　　for(i=1; i<度数.Length; i++) 度数[i] += 度数[i-1]; 　　　　for(i=a.Length-1; i>=0; i--) temp[--度数[a[i]]] =a[i]; 　　　　for(i=0; i<a.Length; i++) a[i]=temp[i]; 　　} 　　private void 度数ソート() 　　{ 　　　　FrequencySort(ref Data,100); 　　} 番号 以下をクリックすると，該当箇所にジャンプします （１） ヒープ （２） 完全２分木の配列による表現 （３） ヒープソート （４） ヒープの構築 1. 基本的なアルゴリズム 2. 基本的なデータ構造 3. 操作を伴うデータ構造 4. 探索 5. 再帰的アルゴリズム 6. ソート 7. 集合 8. 文字列処理 9. 色々なアルゴリズム 上のタイトルをクリックします