６．ソート
整列（ソート：sorting）
６．１ ソートの考え方
与えられたデータの集合を
（１）ソートとは
キーとなる項目の大小関係により，
一定の順序に並び替えること。
昇順
降順
（２）ソートの安定性
等しいキーの位置関係が
ソート後も維持されること
1
2 3 4
5
6
7 8
2
4 7 8
3
5
6 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)
{
初期設定();
}
（４）ソート処理用データ宣言など（２）
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)
{
バブルソート(); ソート後表示();
}
（４）ソート処理用データ宣言など（３）
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)
（４）ソート処理用データ宣言など（４）
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)
{
度数ソート();
ソート後表示(); }
■外部ソート：作業ファイルを用いる例
（４）外部ソート
内部ソート
＆ 出力
内部ソート
（１）
大量データ
マージ
（１）
内部ソート
（２）
マージ
（２）
作業ファイル
（１）
作業ファイル（１）または
作業ファイル（２）に，
最終結果が得られる。
作業ファイル
（２）
６．２ 単純交換法
（１）考え方
比較して交換（前のほうが大きい）
比較するが交換しない（後の方が大きい）
１回目のパス
２回目のパス
０
１
２
３
４
５
６
０
１
２
３
４
５
６
５
３
２
６
１
８
７
１
５
３
２
６
７
８
５
３
２
６
１
７
８
１
５
３
２
６
７
８
５
３
２
６
１
７
８
１
５
３
２
６
７
８
５
３
２
１
６
７
８
１
５
３
２
６
７
８
５
３
１
２
６
７
８
１
５
２
３
６
７
８
５
１
３
２
６
７
８
１
２
５
３
６
７
８
１
５
３
２
６
７
８
（１）考え方（その２）
３回目のパス
４回目のパス
０
１
２
３
４
５
６
０
１
２
３
４
５
６
１
２
５
３
６
７
８
１
２
３
５
６
７
８
１
２
５
３
６
７
８
１
２
３
５
６
７
８
１
２
５
３
６
７
８
１
２
３
５
６
７
８
１
２
５
３
６
７
８
１
２
３
５
６
７
８
値の小さいデータが
上に上がってくるような動きから，
泡が液体中を上にあがってくる様子にたとえて
バブルソート（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]);
}
（２）改良１
４回目のパス
０
１
２
３
４
５
６
１
２
３
５
６
７
８
１
２
３
５
６
７
８
１
２
３
５
６
７
８
（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;
}
}
（３）改良２
もうひとつの例
０
１
２
３
４
５
６
１
２
８
３
６
７
５
１
２
５
３
６
５
７
１
２
８
３
５
６
８
１
２
３
８
６
７
８
１
２
３
８
６
７
８
１
２
３
５
６
７
８
１
２
３
５
６
７
８
交換なし
最後に交換した位置より前は整列済み
プログラム
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;
}
}
（４）その他
次のような例では，改良１，改良２でも早期に
打ち切ることはできない
０
１
２
３
４
５
６
９
２
８
３
６
７
５
奇数パスでは，最小要素を先頭に移動
偶数パスでは，最大要素を末尾に移動
双方向バブルソート（bidirection bubble sort），
シェーカーソート（shaker sort）等と呼ばれる。
６．３ 単純選択法
最小の要素を選択し，先頭の要素と交換する方法。
単純交換法に比べて，交換のためのコストは少なくなるが，
離れた場所を交換するので，安定でないソートとなる。
未ソート部の先頭
既ソート部
未ソート部の最小要素
未ソート部
手順
（１）方法
０
１
２
３
４
５
６
５
３
７
２
１
８
６
１
３
７
２
５
８
６
１
２
７
３
５
８
６
１
２
３
７
５
８
６
１
２
３
５
７
８
６
１
２
３
５
６
８
７
１
２
３
５
６
７
８
プログラム
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;}
}
}
６．４ 単純挿入法
単純挿入ソート（straight insertion sort）：
着目した要素を適当な位置に挿入する作業を繰り返してソート
０
１
２
３
４
５
６
５
３
７
２
１
８
６
３
５
７
２
１
８
６
３
５
７
２
１
８
６
２
３
５
７
１
８
６
１
２
３
５
７
８
６
１
２
３
５
７
８
６
１
２
３
５
６
７
８
シャトルソート（shuttle sort）
とも呼ばれる
挿入の方法
配列の要素を適当な位置に挿入するには，
先頭に達した場合，
または自分と等しいか小さい値に出会った場合，
まで代入操作を繰り返す。
１
２
４
５
３
８
６
４
５
５
８
６
４
４
５
８
６
②
１
２
①
temp
③
１
２
④
３
プログラム
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;
}
}
６．５ シェルソート
単純交換，単純選択，単純挿入ソートは，
繰返しが2重になっているので，
計算量はＯ（Ｎ2）となる。
改良できないか？
単純挿入ソートの改良
［単純挿入ソートの特徴］
(a) ソート済み，またはそれに近いとき高速である。
(b) 挿入先が離れているときは，ずらす回数が多くなる。
最初，なるべく離れた要素をグループ化して，
大まかなソートを行い，そのグループを縮めていく。
(a)の長所を活かし，（b)の短所を補う。
４つずつ離れたグループのソート
（４－ソート）
９
２
５
３
８
単純挿入ソートの改良
７
４
６
４つ離れたグループをソート
８
２
５
３
９
７
４
６
８
２
５
３
８
７
４
６
４つ離れたグループをソート
８
２
５
３
９
７
４
６
８
２
５
３
８
７
４
６
４つ離れたグループをソート
８
２
４
３
９
７
５
６
８
２
４
３
８
７
５
６
４つ離れたグループをソート
８
２
４
３
９
７
５
６
単純挿入ソートの改良
２つずつ離れたグループのソート
（２－ソート）
８
２
４
３
９
７
５
６
２つ離れたグループをソート
４
２
５
３
８
７
９
６
４
２
５
３
８
７
９
６
２つ離れたグループをソート
４
２
５
３
８
６
９
７
単純挿入ソートの改良
最後に単純挿入ソート
ずらす量
４
２
５
３
８
６
９
７
（１）
２
４
５
３
８
６
９
７
（０）
２
４
５
３
８
６
９
７
（２）
２
３
４
５
８
６
９
７
（０）
２
３
４
５
８
６
９
７
（１）
２
３
４
５
６
８
９
７
（０）
２
３
４
５
６
８
９
７
（２）
２
３
４
５
６
７
８
９
ずらした回数計 ６回
単純挿入ソートの改良
単純挿入ソートの場合と比較
ずらす量
９
２
５
３
８
７
４
６
（１）
２
９
５
３
８
７
４
６
（１）
２
５
９
３
８
７
４
６
（２）
２
３
５
９
８
７
４
６
（１）
２
３
５
８
９
７
４
６
（２）
２
３
５
７
８
９
４
６
（４）
２
３
４
５
７
８
９
６
（３）
２
３
４
５
６
７
８
９
ずらした回数計 １４回
プログラム
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;
}
}
増分の選択
増分を４，２，１と変化させたが
９
２
５
３
８
７
４
６
９
８
２
７
９
８
５
４
５
４
２
７
３
６
３
６
２つのグループをあわせたものが
そのまま次のグループになっている!!
増分がお互いの倍数にならないようにして，要素をかき混ぜたほうがよい。
増分＝１，４，１３，４０，１２１ （１から始めて３倍して１を加える）
増分が大きすぎても効果がないことが知られている。
最大増分量は，配列の要素数／９を超えないように決定。
プログラム
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;
}
}
６．６ クイックソート
（１）考え方
グループ分けの基準とする要素（枢軸：pivotと呼ぶ）より小さいグ
ループと大きいグループに分ける作業を繰り返すことによってソー
トする方法。クイックソート（Quick sort）という名前は，他のソートに
比べ高速であるため，考案者のC.A.Hoareによって名付けられた。
９
２
５
３
８
７
４
６
＜６≦
２
３
５
４
６
９
＜４≦
２
３
２
５
６
＜５≦
３
４
７
＜８≦
４
＜３≦
８
７
９
＜７≦
５
６
８
＜９≦
７
８
９
（２）分割の手順
配列両端のポインタ Left，Rightを用意し，以下の操作を行う。
ⅰ）A(Left)≧枢軸となる要素まで右方向にスキャンする。
ⅱ）A(Right)≦枢軸となる要素まで左方向にスキャンする。
ⅲ）A(Left)とA(Right)を交換する。
分割の例
［例］枢軸を６とする。
４
７
５
８
６
２
３
１
Left
４
Right
７
５
８
Left
４
１
６
１
５
８
６
１
３
５
３
６
５
３
１
９
Right
２
交換
Left
４
２
交換
Left
４
９
３
７
９
８
７
９
８
７
９
Right
２
Right
交換
２
６
分割のプログラム
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);
（３）枢軸の選択
最も簡単な方法：
配列の左端，中央，右端のいずれかを枢軸として採用
４
７
５
８
６
２
３
１
９
上記の９を選ぶと，ただ１つの要素とその他の要素に分割される
ので効率が悪い。
中央値を枢軸にすると最も効率が良いが，中央値を求める処理は
時間がかかる → 本末転倒
最悪を避ける方法：
左端，中央，右端の３値の中央値を枢軸にする。
枢軸の選択の例
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;
時間計算量は，理想的にはＯ(N log N)であるが，
ただひとつの要素と，それ以外の要素という分割が続くと
n回の分割が必要となり，最悪時間計算量はＯ(N 2)となる。
（４）ソートの処理
ⅰ）枢軸の選択
ⅱ）配列を分割
ⅲ）分割によるグループの要素数が１でなければ再分割
再分割
分割後 Pl > Prとなっている
ことに注意
Right
Left Pr
再分割
Pｌ Right
Left
再分割
Left
再分割
Pr Pｌ
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);
}
プログラム
（５）非再帰クイックソート
分割の様子
０
1
２
３
４
５
６
７
８
２
５
３
９
７
４
６
０
1
２
３
４
５
６
７
４
２
５
３
９
７
８
６
０
1
２
３
４
３
２
５
４
６
０
1
２
２
３
４
３
５
５
７
６
８
５
７
７
９
６
８
７
９
６
７
８
９
（５）非再帰クイックソート
スタックの動き
（０，７）
をPush
０
（０，７）
を分割
７
（５，７）
をPush
５
７
０
３
（０，３）
を分割
（５，７）
を分割
０
３
（０，１），（２，３）
をPush
２
３
０
１
（０，３），（４，７）
をPush
４
７
０
３
（６，７）
をPush
６
７
０
３
（２，３）
を分割
0
１
（４，７）
を分割
０
３
（６，７）
を分割
０
３
（０，１）
を分割
プログラム（１）
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
{
プログラム（２）
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++;
}
}
}
（６）要素数が異なる場合のスタックの大きさ
先頭側を分割→末尾側を分割の順に行っているが…
どちら側を先に分割しても結果は同じ
比較
要素数が多い方を先に分割（要素数が少ない方を先にＰｕｓｈ）
要素数が少ないほうを先に分割（要素数が多い方を先にＰｕｓｈ）
（６）要素数が異なる場合のスタックの大きさ
分割の様子
０
1
２
３
４
５
６
７
８
２
５
３
９
７
４
６
０
1
２
３
４
５
６
７
３
２
５
８
９
７
４
６
０
1
２
３
４
５
６
７
２
３
５
６
４
７
９
８
２
３
４
５
６
７
５
４
６
７
９
８
２
３
４
５
４
５
６
７
（６）要素数が異なる場合のスタックの大きさ
要素数が少ないほうを先にプッシュ
（０，７）
をPush
０
（０，７）
を分割
（０，１），（２，７）
をPush
７
（２，３），（４，５）
をPush
２
７
０
１
（４，５）
を分割
（２，７）
を分割
０
１
（２，３）
を分割
４
５
２
３
２
３
６
７
６
７
６
７
０
１
０
１
０
１
（６，７），（２，５）
をPush
（２，５）
を分割
２
５
６
７
６
７
０
１
０
１
（６，７）
を分割
（０，１）
を分割
０
０
１
１
（６）要素数が異なる場合のスタックの大きさ
要素数が多いほうを先にプッシュ
（０，７）
をPush
０
（０，７）
を分割
７
（６，７）
を分割
２
５
（２，７），（０，１）
をPush
０
１
２
７
（２，５）
を分割
（０，１）
を分割
２
（２，７）
を分割
７
（２，３），（４，５）
をPush
４
５
２
３
（４，５）
を分割
２
３
（２，５），（６，７）
をPush
６
７
２
５
（２，３）
を分割
（６）要素数が異なる場合のスタックの大きさ
配列の要素数が少ないほど，少ない回数で分割が終了する。
小さいほうの分割を先にやるほうが，
スタックサイズが小さくて済む。
このとき，データ数がNのとき，スタックの深さはlog N
（例） 要素数＝1,000,000のとき，スタックの深さ＝20
６．７ マージソート
（１）ソート済み配列のマージ
ソート済み配列をマージするとソート済みの配列になる。
２
３
０
1
２
３
２
５
７
８
４
５
６
７
３
４
６
９
０
1
２
３
８
９
６．７ マージソート
（２）マージソートの手順
マージソートしたものを
マージする（再帰的）
０
８
２
1
３
７
３
５
４
５
６
７
９
４
２
６
マージソート
３
５
７
マージソート
８
２
４
６
４
２
６
マージ
８
３
７
５
０
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);
}
６．８ ヒープソート
（１）ヒープ
ヒープ（heap）とは，「累積」，「積み重なったもの」
という意味ですが，ここでは，親の値が子供の値より以上であるよう
な完全２分木を意味します。
たとえば，次のような木をヒープといいます。
８
６
５
７
４
３
（２分探索木と異なり，
必ずしも左のノードが右のノードより小さいとは限らない）
６．８ ヒープソート
（２）完全２分木の配列による表現
■ルートをＡ［0］に入れる。
■その直接の左の子をＡ［１］に，右の子をＡ［２］に入れる。
■更に１つ下流に下って左から格納する。
Ａ［０］
Ａ［１］
Ａ［３］
Ａ［７］
配列
Ａ
［０］
Ａ［２］
Ａ［４］
Ａ［５］
Ａ［６］
Ａ［８］
Ａ
［１］
Ａ
［２］
Ａ
［３］
Ａ
［４］
Ａ
［５］
Ａ
［６］
Ａ
［７］
Ａ
［８］
親子の位置関係
■Ａ［Ｉ］の親は，Ａ［（Ｉ－１）／２］
■Ａ［Ｉ］の左の子は，Ａ［Ｉ＊２＋１］
■Ａ［Ｉ］の右の子は，Ａ［Ｉ＊２＋２］
Ａ［０］
Ａ［１］
Ａ［３］
Ａ［７］
配列
Ａ［２］
Ａ［４］
Ａ［５］
Ａ［６］
Ａ［８］
０
１
２
３
４
５
６
７
８
Ａ
［０］
Ａ
［１］
Ａ
［２］
Ａ
［３］
Ａ
［４］
Ａ
［５］
Ａ
［６］
Ａ
［７］
Ａ
［８］
ヒープにおける２分木と配列
［例］
１９
１５
７
４
１０
９
８
配列
５
３
２
０
１
２
３
４
５
６
７
８
９
１９
１５
７
１０
４
３
５
８
９
２
（３）ヒープソート
■ヒープのルートから値を取り出すと最大値が得られる。
■ヒープの最後の要素を先頭に移し，ヒープを再構築する。
■最大値を配列の最後に入れる。
１９
１５
７
４
１０
９
８
配列
５
３
２
０
１
２
３
４
５
６
７
８
９
１９
１５
７
１０
４
３
５
８
９
２
ヒープの再構築
ⅰ）根を取り出し，そこにヒープ最後の要素を移動
１９
２
７
１５
１０
８
４
９
２
３
７
１５
５
１０
８
４
９
３
５
ヒープの再構築
ⅱ）２つの子を比較し，大きい方の子と交換する
ⅲ）リーフに届く,または自分より小さくなるまでⅱ）を繰り返す。
２
１５
７
１５
１０
５
３
４
９
８
７
２
１０
９
８
１５
１５
７
１０
２
８
４
９
５
３
４
３
７
１０
５
９
８
４
２
３
５
（４）ヒープの構築
下流側の部分木からボトムアップ的に積み上げて
ヒープの形にする。
２
２
７
４
９
１５
１９
１０
８
５
３
７
４
９
８
１９
１５
１０
２
２
７
４
１０
８
１９
９
１５
５
３
３
７
４
５
１０
８
１９
９
１５
３
５
ヒープの構築
（再構築と同様の処理となる）
２
１９
７
１９
１０
８
１５
９
４
３
７
１５
５
１０
８
４
９
２
３
５
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);
}
}
プログラム
６．９ 度数ソート
度数ソートでは，累積度数分布表を作成し，
累積度数分布表を利用してソートを行います。
テストの点数など，
取りうる値の範囲が決まっているときに有用です。
０
１
２
３
４
５
６
７
８
２
１
７
１０
４
０
５
３
５
手順
ⅰ）度数分布表の作成
各点数の学生が何人いるかを示す度数分布表を作成する。
ⅱ）累積分布表の作成
その点数以下の学生が何人いるかを示す
累積度数分布表を作成する。
ⅲ）目的配列の作成
原配列と累積度数分布表をつき合わせて
ソート済み配列を作成する。
度数分布表の作成
各点数の学生が何人いるかを示す度数分布表を作成する。
原配列
０
１
２
３
４
５
６
７
８
２
１
６
１０
４
７
５
３
５
度数分布
０
１
２
３
４
５
６
７
８
９
１０
０
１
１
１
１
２
１
１
０
０
１
累積度数分布表の作成
その点数以下の学生が何人いるかを示す度数分布表を作成する。
度数分布
０
１
２
３
４
５
６
７
８
９
１０
０
１
１
１
１
２
１
１
０
０
１
累積度数分布
０
１
２
３
４
５
６
７
８
９
１０
０
１
２
３
４
６
７
８
８
８
９
目的配列の作成
原配列と累積度数分布表をつき合わせて，
ソート済み配列を作成する。
原配列
０
１
２
３
４
５
６
７
８
２
１
６
１０
４
７
５
３
５
累積度数分布
０
１
２
３
４
５
６
７
８
９
１０
０
１
２
３
４
６
７
８
８
８
９
デクリメント
目的配列
０
１
２
３
４
５点の学生は６番（添え字＝５）
５
５
６
７
８
目的配列の作成
同様に，原配列の前の要素を処理
原配列
０
１
２
３
４
５
６
７
８
２
１
６
１０
４
７
５
３
５
累積度数分布
０
１
２
３
４
５
６
７
８
９
１０
０
１
２
３
４
５
７
８
８
８
９
デクリメント
目的配列
０
３点の学生は３番（添え字＝２）
１
２
３
３
４
５
５
６
７
８
目的配列の作成
同様に，原配列の前の要素を処理
原配列
０
１
２
３
４
５
６
７
８
２
１
６
１０
４
７
５
３
５
累積度数分布
０
１
２
３
４
５
６
７
８
９
１０
０
１
２
２
４
５
７
８
８
８
９
デクリメント
５点の学生は５番（添え字＝４）
目的配列
０
１
２
３
３
４
５
５
５
６
７
８
目的配列の作成
同様に，原配列の前の要素を処理
原配列
０
１
２
３
４
５
６
７
８
２
１
６
１０
４
７
５
３
５
累積度数分布
０
１
２
３
４
５
６
７
８
９
１０
０
１
２
２
４
４
７
８
８
８
９
目的配列
０
デクリメント
７点の学生は８番（添え字＝７）
１
２
３
３
４
５
５
５
６
７
７
８
目的配列の作成
同様に，原配列の前の要素を処理
原配列
０
１
２
３
４
５
６
７
８
２
１
６
１０
４
７
５
３
５
累積度数分布
０
１
２
３
４
５
６
７
８
９
１０
０
１
２
２
３
４
７
７
８
８
９
デクリメント
目的配列
０
４点の学生は４番（添え字＝３）
１
２
３
４
５
３
４
５
５
６
７
７
８
目的配列の作成
同様に，原配列の前の要素を処理
原配列
０
１
２
３
４
５
６
７
８
２
１
６
１０
４
７
５
３
５
累積度数分布
０
１
２
３
４
５
６
７
８
９
１０
０
１
２
２
２
４
７
７
８
８
９
デクリメント
目的配列
０
１０点の学生は９番（添え字＝８）
１
２
３
４
５
３
４
５
５
６
７
８
７
９
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 2024 ExpyDoc
