6.ソート 整列(ソート:sorting) 6.1 ソートの考え方 与えられたデータの集合を (1)ソートとは キーとなる項目の大小関係により, 一定の順序に並び替えること。 昇順 降順 (2)ソートの安定性 等しいキーの位置関係が ソート後も維持されること 1 2 3 4 5 6 7 8 2 4 7 8 3 5 6 1 (3)内部ソートと外部ソート ■内部ソート 対象とするデータがメモリ上に格納できる場合 ■外部ソート 対象とするデータが大量すぎて,メモリに格納できない場合 (4)ソート処理用データ宣言など ■フォームの定義 (4)ソート処理用データ宣言など(1) private int[] Data=new int[8]; private void swap(ref int A,ref int B) { int X=A; A=B; B=X;} private void ソート後表示() { listBox2.Items.Clear(); for(int i=0;i<Data.Length;i++) listBox2.Items.Add(i.ToString()+" : "+Data[i].ToString()); } private void Form1_Load(object sender, System.EventArgs e) { 初期設定(); } (4)ソート処理用データ宣言など(2) private void 初期設定() { int i; Random myRandom = new Random(); for(i=0;i<Data.Length;i++)Data[i]=myRandom.Next(10,99); listBox1.Items.Clear(); for(i=0;i<Data.Length;i++) listBox1.Items.Add(i.ToString()+" : " +Data[i].ToString()); listBox2.Items.Clear(); } private void button1_Click(object sender, System.EventArgs e) { バブルソート(); ソート後表示(); } (4)ソート処理用データ宣言など(3) private void button2_Click(object sender, System.EventArgs { 初期設定();} private void button3_Click(object sender, System.EventArgs { バブルソート改良版(); ソート後表示();} private void button4_Click(object sender, System.EventArgs { 単純選択法(); ソート後表示();} private void button5_Click(object sender, System.EventArgs { 単純挿入法(); ソート後表示();} private void button6_Click(object sender, System.EventArgs { シェルソート(); ソート後表示();} private void button7_Click(object sender, System.EventArgs { シェルソート改良版(); ソート後表示();} private void button8_Click(object sender, System.EventArgs { クイックソート(); ソート後表示(); } e) e) e) e) e) e) e) (4)ソート処理用データ宣言など(4) private void button9_Click(object sender, System.EventArgs e) { 非再帰クイックソート(); ソート後表示(); } private void button10_Click(object sender, System.EventArgs e) { ヒープソート(); ソート後表示(); } private void button11_Click(object sender, System.EventArgs e) { マージソート(); ソート後表示(); } private void button12_Click(object sender, System.EventArgs e) { 度数ソート(); ソート後表示(); } ■外部ソート:作業ファイルを用いる例 (4)外部ソート 内部ソート & 出力 内部ソート (1) 大量データ マージ (1) 内部ソート (2) マージ (2) 作業ファイル (1) 作業ファイル(1)または 作業ファイル(2)に, 最終結果が得られる。 作業ファイル (2) 6.2 単純交換法 (1)考え方 比較して交換(前のほうが大きい) 比較するが交換しない(後の方が大きい) 1回目のパス 2回目のパス 0 1 2 3 4 5 6 0 1 2 3 4 5 6 5 3 2 6 1 8 7 1 5 3 2 6 7 8 5 3 2 6 1 7 8 1 5 3 2 6 7 8 5 3 2 6 1 7 8 1 5 3 2 6 7 8 5 3 2 1 6 7 8 1 5 3 2 6 7 8 5 3 1 2 6 7 8 1 5 2 3 6 7 8 5 1 3 2 6 7 8 1 2 5 3 6 7 8 1 5 3 2 6 7 8 (1)考え方(その2) 3回目のパス 4回目のパス 0 1 2 3 4 5 6 0 1 2 3 4 5 6 1 2 5 3 6 7 8 1 2 3 5 6 7 8 1 2 5 3 6 7 8 1 2 3 5 6 7 8 1 2 5 3 6 7 8 1 2 3 5 6 7 8 1 2 5 3 6 7 8 1 2 3 5 6 7 8 値の小さいデータが 上に上がってくるような動きから, 泡が液体中を上にあがってくる様子にたとえて バブルソート(bubble sort), 泡立ちソート等と呼ばれる。 プログラム private void swap(ref int A,ref int B) { int X=A; A=B; B=X; } private void バブルソート() { int i,j; for(i = 0; i < Data.Length - 1; i++) for(j=Data.Length-1; j>i; j--) if(Data[j-1]>Data[j]) swap(ref Data[j-1], ref Data[j]); } (2)改良1 4回目のパス 0 1 2 3 4 5 6 1 2 3 5 6 7 8 1 2 3 5 6 7 8 1 2 3 5 6 7 8 (1回も交換がないので,終わりとしてもよい) プログラム private void バブルソート改良版() { int i,j;bool notExchange; for(i=0;i<Data.Length-1;i++) { notExchange=true; for(j=Data.Length-1; j>i; j--) if(Data[j-1]>Data[j]) { swap(ref Data[j-1], ref Data[j]); notExchange=false; } if(notExchange) break; } } (3)改良2 もうひとつの例 0 1 2 3 4 5 6 1 2 8 3 6 7 5 1 2 5 3 6 5 7 1 2 8 3 5 6 8 1 2 3 8 6 7 8 1 2 3 8 6 7 8 1 2 3 5 6 7 8 1 2 3 5 6 7 8 交換なし 最後に交換した位置より前は整列済み プログラム private void バブルソート改良版2() { int k=0;bool notExchange; n = Data.Length - 1; while (k < n - 1) { int j; int last n - 1; notExchange=true; for(j= n -1; j>k; j--) if(Data[j-1]>Data[j]) { swap(ref Data[j-1], ref Data[j]); last = j; notExchange=false; } if(notExchange) break; k=last; } } (4)その他 次のような例では,改良1,改良2でも早期に 打ち切ることはできない 0 1 2 3 4 5 6 9 2 8 3 6 7 5 奇数パスでは,最小要素を先頭に移動 偶数パスでは,最大要素を末尾に移動 双方向バブルソート(bidirection bubble sort), シェーカーソート(shaker sort)等と呼ばれる。 6.3 単純選択法 最小の要素を選択し,先頭の要素と交換する方法。 単純交換法に比べて,交換のためのコストは少なくなるが, 離れた場所を交換するので,安定でないソートとなる。 未ソート部の先頭 既ソート部 未ソート部の最小要素 未ソート部 手順 (1)方法 0 1 2 3 4 5 6 5 3 7 2 1 8 6 1 3 7 2 5 8 6 1 2 7 3 5 8 6 1 2 3 7 5 8 6 1 2 3 5 7 8 6 1 2 3 5 6 8 7 1 2 3 5 6 7 8 プログラム private void 単純選択法() { int i,j,ID,minDATA; for(i=0;i<Data.Length-1;i++) { minDATA=Data[i];ID=i; for(j=i+1; j<Data.Length; j++) if(minDATA>Data[j]){ minDATA=Data[j];ID=j;} if(ID!=i) { Data[ID]=Data[i];Data[i]=minDATA;} } } 6.4 単純挿入法 単純挿入ソート(straight insertion sort): 着目した要素を適当な位置に挿入する作業を繰り返してソート 0 1 2 3 4 5 6 5 3 7 2 1 8 6 3 5 7 2 1 8 6 3 5 7 2 1 8 6 2 3 5 7 1 8 6 1 2 3 5 7 8 6 1 2 3 5 7 8 6 1 2 3 5 6 7 8 シャトルソート(shuttle sort) とも呼ばれる 挿入の方法 配列の要素を適当な位置に挿入するには, 先頭に達した場合, または自分と等しいか小さい値に出会った場合, まで代入操作を繰り返す。 1 2 4 5 3 8 6 4 5 5 8 6 4 4 5 8 6 ② 1 2 ① temp ③ 1 2 ④ 3 プログラム private void 単純挿入法() { int i,j,Tmp; for(i = 1; i < Data.Length; i++) { Tmp=Data[i]; for(j = i; j > 0 && Data[j-1] > Tmp; j--) Data[j] = Data[j-1]; Data[j]=Tmp; } } 6.5 シェルソート 単純交換,単純選択,単純挿入ソートは, 繰返しが2重になっているので, 計算量はO(N2)となる。 改良できないか? 単純挿入ソートの改良 [単純挿入ソートの特徴] (a) ソート済み,またはそれに近いとき高速である。 (b) 挿入先が離れているときは,ずらす回数が多くなる。 最初,なるべく離れた要素をグループ化して, 大まかなソートを行い,そのグループを縮めていく。 (a)の長所を活かし,(b)の短所を補う。 4つずつ離れたグループのソート (4-ソート) 9 2 5 3 8 単純挿入ソートの改良 7 4 6 4つ離れたグループをソート 8 2 5 3 9 7 4 6 8 2 5 3 8 7 4 6 4つ離れたグループをソート 8 2 5 3 9 7 4 6 8 2 5 3 8 7 4 6 4つ離れたグループをソート 8 2 4 3 9 7 5 6 8 2 4 3 8 7 5 6 4つ離れたグループをソート 8 2 4 3 9 7 5 6 単純挿入ソートの改良 2つずつ離れたグループのソート (2-ソート) 8 2 4 3 9 7 5 6 2つ離れたグループをソート 4 2 5 3 8 7 9 6 4 2 5 3 8 7 9 6 2つ離れたグループをソート 4 2 5 3 8 6 9 7 単純挿入ソートの改良 最後に単純挿入ソート ずらす量 4 2 5 3 8 6 9 7 (1) 2 4 5 3 8 6 9 7 (0) 2 4 5 3 8 6 9 7 (2) 2 3 4 5 8 6 9 7 (0) 2 3 4 5 8 6 9 7 (1) 2 3 4 5 6 8 9 7 (0) 2 3 4 5 6 8 9 7 (2) 2 3 4 5 6 7 8 9 ずらした回数計 6回 単純挿入ソートの改良 単純挿入ソートの場合と比較 ずらす量 9 2 5 3 8 7 4 6 (1) 2 9 5 3 8 7 4 6 (1) 2 5 9 3 8 7 4 6 (2) 2 3 5 9 8 7 4 6 (1) 2 3 5 8 9 7 4 6 (2) 2 3 5 7 8 9 4 6 (4) 2 3 4 5 7 8 9 6 (3) 2 3 4 5 6 7 8 9 ずらした回数計 14回 プログラム private void シェルソート() { int i,j,h, Tmp; for(h = Data.Length / 2 ; h > 0; h /= 2) for(i = h; i < Data.Length; i++) { Tmp=Data[i]; for(j = i - h ; j >= 0 && Data[j] > Tmp; j -= h) Data[j + h]=Data[j]; Data[j + h]=Tmp; } } 増分の選択 増分を4,2,1と変化させたが 9 2 5 3 8 7 4 6 9 8 2 7 9 8 5 4 5 4 2 7 3 6 3 6 2つのグループをあわせたものが そのまま次のグループになっている!! 増分がお互いの倍数にならないようにして,要素をかき混ぜたほうがよい。 増分=1,4,13,40,121 (1から始めて3倍して1を加える) 増分が大きすぎても効果がないことが知られている。 最大増分量は,配列の要素数/9を超えないように決定。 プログラム private void シェルソート改良版() { int i, j, h, Tmp; for(h = 1; h < Data.Length / 9; h = h * 3 + 1); for( ; h>0; h /= 3) for(i = h; i < Data.Length; i++) { Tmp = Data[i]; for(j = i - h ; j >= 0 && Data[j] > Tmp; j -= h) Data[j + h] = Data[j]; Data[j + h]=Tmp; } } 6.6 クイックソート (1)考え方 グループ分けの基準とする要素(枢軸:pivotと呼ぶ)より小さいグ ループと大きいグループに分ける作業を繰り返すことによってソー トする方法。クイックソート(Quick sort)という名前は,他のソートに 比べ高速であるため,考案者のC.A.Hoareによって名付けられた。 9 2 5 3 8 7 4 6 <6≦ 2 3 5 4 6 9 <4≦ 2 3 2 5 6 <5≦ 3 4 7 <8≦ 4 <3≦ 8 7 9 <7≦ 5 6 8 <9≦ 7 8 9 (2)分割の手順 配列両端のポインタ Left,Rightを用意し,以下の操作を行う。 ⅰ)A(Left)≧枢軸となる要素まで右方向にスキャンする。 ⅱ)A(Right)≦枢軸となる要素まで左方向にスキャンする。 ⅲ)A(Left)とA(Right)を交換する。 分割の例 [例]枢軸を6とする。 4 7 5 8 6 2 3 1 Left 4 Right 7 5 8 Left 4 1 6 1 5 8 6 1 3 5 3 6 5 3 1 9 Right 2 交換 Left 4 2 交換 Left 4 9 3 7 9 8 7 9 8 7 9 Right 2 Right 交換 2 6 分割のプログラム int pleft = 0; // 左カーソル int pright = n - 1; // 右カーソル int x = a[(pleft + pright) / 2]; // 中央値を枢軸とする do { while(a[pleft] < x) pleft++; // 左カーソルの走査 while(a[pright] > x) pright--; // 右カーソルの走査 if (pleft <= pright) { swap(ref a[pleft], ref a[pright]); // 交換 pleft++; pright--; } } while (pleft <= pright); (3)枢軸の選択 最も簡単な方法: 配列の左端,中央,右端のいずれかを枢軸として採用 4 7 5 8 6 2 3 1 9 上記の9を選ぶと,ただ1つの要素とその他の要素に分割される ので効率が悪い。 中央値を枢軸にすると最も効率が良いが,中央値を求める処理は 時間がかかる → 本末転倒 最悪を避ける方法: 左端,中央,右端の3値の中央値を枢軸にする。 枢軸の選択の例 int x = a[(pleft + pright) / 2]; int x1 = a[pleft]; int x2 = a[pright]; if((x <= x1 && x1 <= x2)||(x2 <= x1 && x1 <= x)) x = x1; if((x <= x2 && x2 <= x1)||(x1 <= x2 && x2 <= x)) x = x2; 時間計算量は,理想的にはO(N log N)であるが, ただひとつの要素と,それ以外の要素という分割が続くと n回の分割が必要となり,最悪時間計算量はO(N 2)となる。 (4)ソートの処理 ⅰ)枢軸の選択 ⅱ)配列を分割 ⅲ)分割によるグループの要素数が1でなければ再分割 再分割 分割後 Pl > Prとなっている ことに注意 Right Left Pr 再分割 Pl Right Left 再分割 Left 再分割 Pr Pl Right private void Quick(ref int [] a,int left, int right) { int pleft =left; int pright =right; int x = a[(pleft + pright) / 2]; // 枢軸の選択 int x1 = a[pleft];int x2 = a[pright]; if((x <= x1 && x1 <= x2)||(x2 <= x1 && x1 <= x)) x=x1; if((x <= x2 && x2 <= x1)||(x1 <= x2 && x2 <= x)) x=x2; do { while(a[pleft] < x) pleft++; // 枢軸以上の走査 while(a[pright] > x) pright--; // 枢軸以下の走査 if (pleft <= pright) { swap(ref a[pleft], ref a[pright]); // 枢軸以上,以下の交換 pleft++; pright--; } } while (pleft <= pright); if(left < pright) Quick(ref a, left, pright); if(pleft < right ) Quick(ref a, pleft, right); } private void クイックソート() { Quick(ref Data, 0, Data.Length-1); } プログラム (5)非再帰クイックソート 分割の様子 0 1 2 3 4 5 6 7 8 2 5 3 9 7 4 6 0 1 2 3 4 5 6 7 4 2 5 3 9 7 8 6 0 1 2 3 4 3 2 5 4 6 0 1 2 2 3 4 3 5 5 7 6 8 5 7 7 9 6 8 7 9 6 7 8 9 (5)非再帰クイックソート スタックの動き (0,7) をPush 0 (0,7) を分割 7 (5,7) をPush 5 7 0 3 (0,3) を分割 (5,7) を分割 0 3 (0,1),(2,3) をPush 2 3 0 1 (0,3),(4,7) をPush 4 7 0 3 (6,7) をPush 6 7 0 3 (2,3) を分割 0 1 (4,7) を分割 0 3 (6,7) を分割 0 3 (0,1) を分割 プログラム(1) private void 非再帰クイックソート() { int left, right; int ptr = 0; int[] leftStack =new int[10]; int[] rightStack=new int[10]; leftStack[0] = 0; rightStack[0] = Data.Length-1; ptr++; while (ptr-- > 0) { int pleft =left = leftStack[ptr]; int pright =right = rightStack[ptr]; int x = Data[(pleft + pright) / 2]; int x1 = Data[pleft];int x2 = Data[pright]; if((x <= x1 && x1 <= x2)||(x2 <= x1 && x1 <= x)) x=x1; if((x <= x2 && x2 <= x1)||(x1 <= x2 && x2 <= x)) x=x2; do { プログラム(2) while(Data[pleft] < x) pleft++; while(Data[pright] > x) pright--; if (pleft <= pright) { swap(ref Data[pleft], ref Data[pright]); pleft++; pright--; } } while (pleft <= pright); if(left < pright) { leftStack[ptr] = left; rightStack[ptr] = pright; ptr++; } if(pleft < right ) { leftStack[ptr] = pleft; rightStack[ptr] = right; ptr++; } } } (6)要素数が異なる場合のスタックの大きさ 先頭側を分割→末尾側を分割の順に行っているが… どちら側を先に分割しても結果は同じ 比較 要素数が多い方を先に分割(要素数が少ない方を先にPush) 要素数が少ないほうを先に分割(要素数が多い方を先にPush) (6)要素数が異なる場合のスタックの大きさ 分割の様子 0 1 2 3 4 5 6 7 8 2 5 3 9 7 4 6 0 1 2 3 4 5 6 7 3 2 5 8 9 7 4 6 0 1 2 3 4 5 6 7 2 3 5 6 4 7 9 8 2 3 4 5 6 7 5 4 6 7 9 8 2 3 4 5 4 5 6 7 (6)要素数が異なる場合のスタックの大きさ 要素数が少ないほうを先にプッシュ (0,7) をPush 0 (0,7) を分割 (0,1),(2,7) をPush 7 (2,3),(4,5) をPush 2 7 0 1 (4,5) を分割 (2,7) を分割 0 1 (2,3) を分割 4 5 2 3 2 3 6 7 6 7 6 7 0 1 0 1 0 1 (6,7),(2,5) をPush (2,5) を分割 2 5 6 7 6 7 0 1 0 1 (6,7) を分割 (0,1) を分割 0 0 1 1 (6)要素数が異なる場合のスタックの大きさ 要素数が多いほうを先にプッシュ (0,7) をPush 0 (0,7) を分割 7 (6,7) を分割 2 5 (2,7),(0,1) をPush 0 1 2 7 (2,5) を分割 (0,1) を分割 2 (2,7) を分割 7 (2,3),(4,5) をPush 4 5 2 3 (4,5) を分割 2 3 (2,5),(6,7) をPush 6 7 2 5 (2,3) を分割 (6)要素数が異なる場合のスタックの大きさ 配列の要素数が少ないほど,少ない回数で分割が終了する。 小さいほうの分割を先にやるほうが, スタックサイズが小さくて済む。 このとき,データ数がNのとき,スタックの深さはlog N (例) 要素数=1,000,000のとき,スタックの深さ=20 6.7 マージソート (1)ソート済み配列のマージ ソート済み配列をマージするとソート済みの配列になる。 2 3 0 1 2 3 2 5 7 8 4 5 6 7 3 4 6 9 0 1 2 3 8 9 6.7 マージソート (2)マージソートの手順 マージソートしたものを マージする(再帰的) 0 8 2 1 3 7 3 5 4 5 6 7 9 4 2 6 マージソート 3 5 7 マージソート 8 2 4 6 4 2 6 マージ 8 3 7 5 0 1 2 3 9 4 5 6 7 9 再帰的な動きを 含めたデータの流れ 6.7 マージソート (2)マージソートの手順 マージ (3) (2) (1) 配列 プログラム private void MergeSort(ref int[] a, int 左, int 右) { if(左 <右) { int 中央 =(左 + 右)/2; MergeSort(ref a, 左, 中央); MergeSort(ref a, 中央 + 1, 右); int[] temp= new int[右 - 左 + 1]; int p=0; int i; int j=0; int k=左; for(i=左; i <= 中央; i++) temp[p++]=a[i]; while(i <= 右 && j<p) a[k++]=(temp[j]<=a[i]) ? temp[j++]:a[i++]; while(j < p) a[k++] = temp[j++]; } } private void マージソート() { MergeSort(ref Data,0, Data.Length-1); } 6.8 ヒープソート (1)ヒープ ヒープ(heap)とは,「累積」,「積み重なったもの」 という意味ですが,ここでは,親の値が子供の値より以上であるよう な完全2分木を意味します。 たとえば,次のような木をヒープといいます。 8 6 5 7 4 3 (2分探索木と異なり, 必ずしも左のノードが右のノードより小さいとは限らない) 6.8 ヒープソート (2)完全2分木の配列による表現 ■ルートをA[0]に入れる。 ■その直接の左の子をA[1]に,右の子をA[2]に入れる。 ■更に1つ下流に下って左から格納する。 A[0] A[1] A[3] A[7] 配列 A [0] A[2] A[4] A[5] A[6] A[8] A [1] A [2] A [3] A [4] A [5] A [6] A [7] A [8] 親子の位置関係 ■A[I]の親は,A[(I-1)/2] ■A[I]の左の子は,A[I*2+1] ■A[I]の右の子は,A[I*2+2] A[0] A[1] A[3] A[7] 配列 A[2] A[4] A[5] A[6] A[8] 0 1 2 3 4 5 6 7 8 A [0] A [1] A [2] A [3] A [4] A [5] A [6] A [7] A [8] ヒープにおける2分木と配列 [例] 19 15 7 4 10 9 8 配列 5 3 2 0 1 2 3 4 5 6 7 8 9 19 15 7 10 4 3 5 8 9 2 (3)ヒープソート ■ヒープのルートから値を取り出すと最大値が得られる。 ■ヒープの最後の要素を先頭に移し,ヒープを再構築する。 ■最大値を配列の最後に入れる。 19 15 7 4 10 9 8 配列 5 3 2 0 1 2 3 4 5 6 7 8 9 19 15 7 10 4 3 5 8 9 2 ヒープの再構築 ⅰ)根を取り出し,そこにヒープ最後の要素を移動 19 2 7 15 10 8 4 9 2 3 7 15 5 10 8 4 9 3 5 ヒープの再構築 ⅱ)2つの子を比較し,大きい方の子と交換する ⅲ)リーフに届く,または自分より小さくなるまでⅱ)を繰り返す。 2 15 7 15 10 5 3 4 9 8 7 2 10 9 8 15 15 7 10 2 8 4 9 5 3 4 3 7 10 5 9 8 4 2 3 5 (4)ヒープの構築 下流側の部分木からボトムアップ的に積み上げて ヒープの形にする。 2 2 7 4 9 15 19 10 8 5 3 7 4 9 8 19 15 10 2 2 7 4 10 8 19 9 15 5 3 3 7 4 5 10 8 19 9 15 3 5 ヒープの構築 (再構築と同様の処理となる) 2 19 7 19 10 8 15 9 4 3 7 15 5 10 8 4 9 2 3 5 private void ヒープ化(ref int[] a, int 左, int 右) { int AA = a[左]; int 子; int 親; for(親 = 左; 親 < (右 + 1)/2 ; 親 = 子) { int 左の子 = 親 * 2 + 1; int 右の子 = 左の子 + 1; 子 = (右の子 <= 右 && a[右の子]>a[左の子]) ? 右の子 : 左の子; if(AA >= a[子]) break; a[親]=a[子]; } a[親]=AA; } private void ヒープソート() { int i; for (i = (Data.Length - 1) / 2;i >= 0; i--) ヒープ化(ref Data, i, Data.Length - 1); for (i = Data.Length - 1 ;i > 0; i--) { swap(ref Data[0], ref Data[i]); ヒープ化(ref Data, 0, i-1); } } プログラム 6.9 度数ソート 度数ソートでは,累積度数分布表を作成し, 累積度数分布表を利用してソートを行います。 テストの点数など, 取りうる値の範囲が決まっているときに有用です。 0 1 2 3 4 5 6 7 8 2 1 7 10 4 0 5 3 5 手順 ⅰ)度数分布表の作成 各点数の学生が何人いるかを示す度数分布表を作成する。 ⅱ)累積分布表の作成 その点数以下の学生が何人いるかを示す 累積度数分布表を作成する。 ⅲ)目的配列の作成 原配列と累積度数分布表をつき合わせて ソート済み配列を作成する。 度数分布表の作成 各点数の学生が何人いるかを示す度数分布表を作成する。 原配列 0 1 2 3 4 5 6 7 8 2 1 6 10 4 7 5 3 5 度数分布 0 1 2 3 4 5 6 7 8 9 10 0 1 1 1 1 2 1 1 0 0 1 累積度数分布表の作成 その点数以下の学生が何人いるかを示す度数分布表を作成する。 度数分布 0 1 2 3 4 5 6 7 8 9 10 0 1 1 1 1 2 1 1 0 0 1 累積度数分布 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 6 7 8 8 8 9 目的配列の作成 原配列と累積度数分布表をつき合わせて, ソート済み配列を作成する。 原配列 0 1 2 3 4 5 6 7 8 2 1 6 10 4 7 5 3 5 累積度数分布 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 6 7 8 8 8 9 デクリメント 目的配列 0 1 2 3 4 5点の学生は6番(添え字=5) 5 5 6 7 8 目的配列の作成 同様に,原配列の前の要素を処理 原配列 0 1 2 3 4 5 6 7 8 2 1 6 10 4 7 5 3 5 累積度数分布 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 7 8 8 8 9 デクリメント 目的配列 0 3点の学生は3番(添え字=2) 1 2 3 3 4 5 5 6 7 8 目的配列の作成 同様に,原配列の前の要素を処理 原配列 0 1 2 3 4 5 6 7 8 2 1 6 10 4 7 5 3 5 累積度数分布 0 1 2 3 4 5 6 7 8 9 10 0 1 2 2 4 5 7 8 8 8 9 デクリメント 5点の学生は5番(添え字=4) 目的配列 0 1 2 3 3 4 5 5 5 6 7 8 目的配列の作成 同様に,原配列の前の要素を処理 原配列 0 1 2 3 4 5 6 7 8 2 1 6 10 4 7 5 3 5 累積度数分布 0 1 2 3 4 5 6 7 8 9 10 0 1 2 2 4 4 7 8 8 8 9 目的配列 0 デクリメント 7点の学生は8番(添え字=7) 1 2 3 3 4 5 5 5 6 7 7 8 目的配列の作成 同様に,原配列の前の要素を処理 原配列 0 1 2 3 4 5 6 7 8 2 1 6 10 4 7 5 3 5 累積度数分布 0 1 2 3 4 5 6 7 8 9 10 0 1 2 2 3 4 7 7 8 8 9 デクリメント 目的配列 0 4点の学生は4番(添え字=3) 1 2 3 4 5 3 4 5 5 6 7 7 8 目的配列の作成 同様に,原配列の前の要素を処理 原配列 0 1 2 3 4 5 6 7 8 2 1 6 10 4 7 5 3 5 累積度数分布 0 1 2 3 4 5 6 7 8 9 10 0 1 2 2 2 4 7 7 8 8 9 デクリメント 目的配列 0 10点の学生は9番(添え字=8) 1 2 3 4 5 3 4 5 5 6 7 8 7 9 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); ソート後表示(); }
© Copyright 2025 ExpyDoc