整列アルゴリズムの基礎
この回の要点 整列とは? 整列処理の意味 整列の種類 整列の計算量 整列の安定性 単純な整列アルゴリズム バブルソート 選択ソート 挿入ソート それぞれのソートの特徴と実装
整列 (Sorting) とは 整列という操作 レコードの集まりを キーの値の大小関係に従って並べ替える操作 小さい 大きい = 昇順 (ascending order) 大きい 小さい = 降順 (descending order) データには 同じキーを持つものがあってもよい 同じキーのデータは連続して整列される 整列アルゴリズムの種類 比較による整列 バブルソート 選択ソート 挿入ソート :O(n 2 ) シェルソート :O(n 1.5 ) ヒープソート マージソート クイックソート :O(n log n) 比較によらない整列 ( デジタルソート ) バケットソート ( ビンソート ) 分布数え上げソート 基数ソート :O(n)
整列の計算量 比較による整列 n 個のデータを整列するときに必要な処理 2 つのデータの大小を判定する ( 比較 ) 必要ならばそれらを入れ替える ( 交換 ) アルゴリズムによって 2 つの処理の回数の比率が異なる 扱うデータがどちらにコストがかかるか によって使い分ける データのサイズが大きい場合 データそのものを交換するのにコストがかかる キーの構造が複雑な場合 比較にコストがかかる 計算量だけでなく 定数項部分も重要 高速なアルゴリズムは処理が複雑である傾向がある n が小さいときは 単純なアルゴリズムのほうが速いこともある 比較によらない整列 時間的には O(n) で整列可能であるが メモリ量も O(n) である 時間的にも O(n) と O(n log n) とは 実用的にはそれほど差はない
O(n) と O(n log n) と O(n 2 ) との比較 1E+13 1E+11 1E+09 n n log(n) n*n 10000000 100000 1000 10 0.1 1 100 10000 1000000
安定な整列 安定な (stable) 整列とは 同じキーを持つデータがある場合に それらの順序関係が保たれる整列 すべての整列アルゴリズムが安定であるとは限らない 単純な ( 遅い ) アルゴリズムは安定の傾向 複雑な ( 速い ) アルゴリズムは非安定の傾向 ただし サブキーを利用することで 確実に安定にできる 安定性の利点 複数のエントリーを持つレコードを 1 つのキーによって整列するような場合 安定なソートは必ずこうなる 整列前 : 7 9 5 a 4 8 5 b 2 整列後 1: 2 4 5 a 5 b 7 8 9 非安定なソートはどちらになるかわからない 整列後 2: 2 4 5 b 5 a 7 8 9
単純な整列アルゴリズム 以下の 3 種類 バブルソート 選択ソート 挿入ソート いずれも O(n 2 ) の計算量 プログラムとして実装した場合 データ数 n に対して 2 重の for ループ構造となる n が大きいと遅くて使いものにならない アルゴリズムが簡単ですぐに実装できる 少ないデータを整列するには重宝
ソート関数の形 任意のポインタの配列を並べ替える関数 sortxxxxx( 配列, サイズ, 比較関数 ) XXXXX は並べ替えのタイプ sortbubble() sortselection() sortinsertion() など 配列は任意のポインタの配列 サイズは配列の要素数 比較関数 int *compare(void *d1,void *d2) d1=d2 ならばゼロ d1<d2 ならば負の数 d1>d2 ならば正の数 を返す
Sort.h #ifndef Sort h #define Sort h /*** *** 並べ替え用 ***/ #include <stdio.h> #include <stdlib.h> 整列データ データ数 比較関数 // プロトタイプ宣言 void sortbubble(void*,int,int(*)(void*,void*)); void sortselection(void*,int,int(*)(void*,void*)); void sortinsertion(void*,int,int(*)(void*,void*)); #endif // Sort h
バブルソート 原理 配列の後ろから先頭に向かってスキャンし 隣り合う要素の大小関係が逆なら入れ替える 6 2 7 5 4 1 3 4 1 1 5 1 7 1 3 2 1 1 6 2 7 5 4 3 4 3 3 5 3 7 3 2 2 6 1 3 7 5 4 4 5 4 7 4 3 時間
Sort.cc /*** ソートの実装 ***/ #include "Sort.h" // バブルソート void sortbubble(void *d0,int s,int (*comp)(void*,void*)){ void **d=(void**)d0; 次のスライドで説明 for(int i=0;i<s-1;i++){ for(int j=s-1;j>i;j--){ if(comp(d[j-1],d[j])>0){ void *t=d[j]; d[j]=d[j-1]; d[j-1]=t; 3 2 1
整列データの受け渡し 整列データ配列 整列するためのデータ 任意のポインタである void* の配列 これは void** と表すことができる 実際に並べ替えるデータ PD のポインタ配列である PD** など PD** から void** への変換が必要となる この変換は暗黙には行われない void** 渡すデータ void* void* void* void* void* 任意 任意 そのための工夫 sortxxxxx(void*,int, ) のように void* で受ける void* は任意のポインタであるから PD** でも良い これを受け取った後に void** にキャストする ただし これによりコンパイラによる型チェックの恩恵にはあずかれなくなる 実際のデータ
整列データの受け渡し 整列関数 PD** void sortxxxxx(void *d0, ){ void **d=(void**)d0; void** void* void* void* void* void* void* void* void* PD* PD* PD* PD* PD* PD* PD* PD* 整列するデータ 関数の中では void* の配列として取り扱う 山田 18 森 55 中村 33 今井 60
バブルソートの計算量 二重ループ構造 (1 と 2) 1 のループは n-1 回 O(n-1) 2 のループは 平均 n/2 回 O(n/2) 3 の処理は n に無関係 O(1) 計算量 O(n-1) O(n/2) O(1)=O(n 2 ) となる 安定な整列アルゴリズム 前の要素が大きければ入れ替える 等しい場合は入れ替わらない 等しい要素の順番は保存される データの交換回数が多い ループ 2 の中で データが上位に上がるとデータの交換が起こる 処理効率の低下
TestSort1.cc /*** *** 整列のテスト ***/ #include "Sort.h" #include "PD.h" // 比較関数 int comp(void *d1,void *d2){ PD *pd1=(pd*)d1; PD *pd2=(pd*)d2; return pd1->age-pd2->age; // 表示 void print(pd **d,int s){ for(int i=0;i<s;i++) printf("%s(%d)-",d[i]->name,d[i]->age); printf(" n"); 続く
TestSort1.cc // メイン int main(int argc,char **argv){ PD *data[6]; data[0]=makepd(" 山田 ",18); data[1]=makepd(" 森 ",55); data[2]=makepd(" 中村 ",33); data[3]=makepd(" 石田 ",27); data[4]=makepd(" 東村 ",31); data[5]=makepd(" 牧 ",12); print(data,6); // 並べ換える前の表示 sortbubble(data,6,comp); // 並べ換え print(data,6); // 並べ換えた後の表示
実行結果 $./TestSort1 山田 (18)- 森 (55)- 中村 (33)- 石田 (27)- 東村 (31)- 牧 (12)- 牧 (12)- 山田 (18)- 石田 (27)- 東村 (31)- 中村 (33)- 森 (55)- 年齢順が若いに並んでいる
選択ソート 原理 整列されていない部分から最小の要素を選び それを先頭に移動する a[0]~a[n-1] の最小の要素を a[0] と交換 a[1]~a[n-1] の最小の要素を a[1] と交換 a[2]~a[n-1] の最小の要素を a[2] と交換 a[n-2]~a[n-1] の最小の要素を a[n-2] と交換 整列済み 未整列 最小を探す 整列済み 先頭に持ってくる ( 交換 )
Sort.cc( 続き ) // 選択ソート void sortselection(void *d0,int s,int (*comp)(void*,void*)){ void **d=(void**)d0; for(int i=0;i<s-1;i++){ int min=i; for(int j=i+1;j<s;j++){ if(comp(d[j],d[min])<0) min=j; void *t=d[i]; d[i]=d[min]; d[min]=t; 4 3 2 1
選択ソートの計算量 二重ループ構造 1 のループは n-1 回 O(n-1) 2 のループは 平均 n/2 回 O(n/2) 3 の処理は n に無関係 O(1) 4 の処理も n に無関係 O(1) 計算量 O(n-1) O(n/2) O(1) O(1)=O(n 2 ) となる 非安定な整列アルゴリズム 先頭要素との交換時に 同じ値を持つ要素の並びが変化する データの交換回数が少ない ループ 1 が 1 回まわると 交換が 1 回だけ起こる バブルソートより高速
挿入ソート 原理 配列の一部を整列済みにし 残りの要素を 1 つずつその中の適切な位置に挿入する 整列前 1 回ループ後 2 回ループ後 3 回ループ後 4 回ループ後 5 回ループ後 14 8 3 18 21 4 31 7 11 24 16 8 14 3 18 21 4 31 7 11 24 16 3 8 14 18 21 4 31 7 11 24 16 3 8 14 18 21 4 31 7 11 24 16 3 8 14 18 21 4 31 7 11 24 16 3 4 8 14 18 21 31 7 11 24 16 整列済み 先頭要素だけ整列済み整列済みに 8を挿入 ( 比較 1 回 ) 整列済みに 3を挿入 ( 比較 2 回 ) 整列済みに 18を挿入 ( 比較 1 回 ) 整列済みに 21を挿入 ( 比較 1 回 ) 整列済みに 4を挿入 ( 比較 4 回 )
InsertionSort.java // 挿入ソート void sortinsertion(void *d0,int s,int (*comp)(void*,void*)){ void **d=(void**)d0; for(int i=1;i<s;i++){ for(int j=i;j>0 && comp(d[j-1],d[j])>0;j--){ void *t=d[j]; d[j]=d[j-1]; 3 2 1 d[j-1]=t;
挿入ソートの計算量 二重ループ構造 1 のループは n-1 回 O(n-1) 2 のループは 平均 n/2 回 O(n/2) 3 の処理は n に無関係 O(1) 計算量 O(n-1) O(n/2) O(1) =O(n 2 ) となる 安定な整列アルゴリズム 挿入するとき 1 つ前の要素が大きければ入れ替える 同じの場合は入れ替えないので 同じ要素の順番は保持される ほとんど整列済みのデータに有利 既に並んでいるデータについては比較と交換が発生しない この場合 ループ 2 は 1 回もまわらない ほとんど整列済みのデータに対しては ほぼ O(n) で整列可能
単純な整列アルゴリズムの比較 実験用プログラム 3 つのソートを実行し 以下の情報を測定 実行時間 データの比較回数 データの交換回数 Sort.ccに変数を追加する ( 後で ) 与えるデータ データ数を可変 (200 個 ~10000 個 ) データの分布を可変 ( ランダム ほぼ整列済み )
比較と交換の回数のカウント (1) Sort.cc にカウント用の変数を追加 整列前に 0 に初期化する 各アルゴリズムの sortxxxx() 関数内で 比較と交換の回数をカウント /*** *** ソートの実装 ***/ #include "Sort.h" int comp_count; int exchg_count; // 比較回数 // 交換回数 Sort.h の中で extern 宣言してないので Sort.cc の中でしか使えない変数 続く
比較と交換の回数のカウント (2) // バブルソート void sortbubble(void *d0,int s,int (*comp)(void*,void*)){ comp_count=exchg_count=0; void **d=(void**)d0; for(int i=0;i<s-1;i++){ for(int j=s-1;j>i;j--){ comp_count++; if(comp(d[j-1],d[j])>0){ exchg_count++; void *t=d[j]; d[j]=d[j-1]; d[j-1]=t; 続く
比較と交換の回数のカウント (3) // 選択ソート void sortselection(void *d0,int s,int (*comp)(void*,void*)){ comp_count=exchg_count=0; void **d=(void**)d0; for(int i=0;i<s-1;i++){ int min=i; for(int j=i+1;j<s;j++){ comp_count++; if(comp(d[j],d[min])<0) min=j; exchg_count++; void *t=d[i]; d[i]=d[min]; d[min]=t; 続く
比較と交換の回数のカウント (4) // 挿入ソート void sortinsertion(void *d0,int s,int (*comp)(void*,void*)){ comp_count=exchg_count=0; void **d=(void**)d0; for(int i=1;i<s;i++){ for(int j=i;j>0;j--){ comp_count++; if(comp(d[j-1],d[j])>0){ exchg_count++; void *t=d[j]; d[j]=d[j-1]; d[j-1]=t; else break; カウントするために 判断構造を少し変えた本質的には同じ 続く
比較と交換の回数のカウント (5) 各回数を得るための関数を追加 // 比較回数を得る int getcompcount(){ return comp_count; // 交換回数を得る int getexchgcount(){ return exchg_count;
比較と交換の回数のカウント (6) Sort.h にプロトタイプ宣言を追加 #ifndef Sort h #define Sort h /*** *** 並べ替え用 ***/ #include <stdio.h> #include <stdlib.h> // プロトタイプ宣言 void sortbubble(void*,int,int(*)(void*,void*)); void sortselection(void*,int,int(*)(void*,void*)); void sortinsertion(void*,int,int(*)(void*,void*)); int getcompcount(); int getexchgcount(); #endif // Sort h
テスト用 TestSort2.cc /*** *** 並べ換えのテスト 2 ***/ #include "Sort.h" #include "PD.h" #include <string.h> #include <time.h> // 比較関数 // 名前で比較し 同じなら年齢で比較する int compare(void *d1,void *d2){ PD *pd1=(pd*)d1; PD *pd2=(pd*)d2; int c=strcmp(pd1->name,pd2->name); if(c==0) return pd1->age-pd2->age; return c; 続く
テスト用 TestSort2.cc // メイン int main(int argc,char **argv){ int loop=1; double rand_rate=1.0; // 引数処理 if(argc!=3 && argc!=4 && argc!=5){ fprintf(stderr, "Usage: %s type max [rand=1.0] [loop=1]",argv[0]); exit(1); int type=atoi(argv[1]); int max=atoi(argv[2]); if(argc>=4) rand_rate=atof(argv[3]); if(argc>=5) loop=atoi(argv[4]); PD **data=(pd**)malloc(max*sizeof(pd*)); srand(time(null)); 続く
テスト用 TestSort2.cc // 実験 double lap=0; double comp_count=0; double exchg_count=0; for(int i=0;i<loop;i++){ // シリアルデータの準備 char s[]={ 'a','a','a','a','a',0 ; for(int i=0;i<max;i++){ int a=rand()%60+10; // 年齢はランダム data[i]=makepd(s,a); for(int j=4;j>=0;j--){ if(s[j]<'z'){ s[j]++; break; s[j]='a'; 続く
テスト用 TestSort2.cc // シャッフル int c=(int)(max*rand_rate); for(int i=0;i<c;i++){ int r1=(int)(((double)rand()/rand_max)*max); int r2=(int)(((double)rand()/rand_max)*max); PD *t=data[r1]; data[r1]=data[r2]; data[r2]=t; 続く
テスト用 TestSort2.cc // 並べ替え clock_t t1=clock(); switch(type){ case 0: sortbubble(data,max,compare); break; case 1: sortselection(data,max,compare); break; case 2: sortinsertion(data,max,compare); break; clock_t t2=clock(); lap+=((double)t2-t1)/clocks_per_sec; comp_count+=getcompcount(); exchg_count+=getexchgcount(); // 結果を表示 ( 時間 比較回数の平均 交換回数の平均 ) printf("%f %f %f ",lap*1000,comp_count/loop,exchg_count/loop);
データ数と並べ替え時間 1000000 100000 10000 b-lap s-lap i-lap n^2/100 1000 100 10 1 100 1000 10000
データ数と比較回数 100000000 10000000 1000000 100000 10000 b-comp s-comp i-cmop 1000 100 1000 10000
データ数と交換回数 100000000 10000000 1000000 b-exchg s-exchg i-exchg 100000 10000 1000 100 100 1000 10000
比較回数 交換回数 選択ソートはデータの交換回数が少ない 挿入ソートはデータの比較回数が少ない num b-lap b-comp b-exchg s-lap s-comp s-exchg i-lap i-cmop i-exchg 200 15 19900 8882.7 0 19900 199 0 9078.65 8882.7 300 15 44850 20223.45 15 44850 299 0 20519 20223.45 500 46 124750 56795.45 31 124750 499 15 57289.95 56795.45 700 32 244650 110607.8 62 244650 699 31 111303.3 110607.8 1000 171 499500 223885.2 140 499500 999 78 224880.3 223885.2 2000 703 1999000 907912.4 546 1999000 1999 265 904197.5 902201.7 3000 1593 4498500 2035679 1203 4498500 2999 546 2032459 2029464 5000 4452 12497500 5659682 3296 12497500 4999 1453 5642875 5637880 7000 8751 24496500 11069605 6422 24496500 6999 2859 11110157 11103161 10000 18300 49995000 22607757 13332 49995000 9999 5828 22507657 22497662
ほぼ揃ったデータの整列 100000 ほぼ揃っている ランダム 10000 1000 100 b-lap s-lap i-lap 0 0.2 0.4 0.6 0.8 1
ほぼそろったデータに対する比較回数 交換回数 データ数は 10000 に固定 挿入ソートは 比較回数が極端に少ない それに応じて 交換回数も少なくなる rand b-lap b-comp b-exchg s-lap s-comp s-exchg i-lap i-cmop i-exchg 0.01 11453 49995000 657297 8736 49995000 9999 171 650484 640485 0.05 12141 49995000 3085772 9079 49995000 9999 749 3052251 3042252 0.1 12814 49995000 5715629 9623 49995000 9999 1499 5780676 5770677 0.2 14172 49995000 10128342 10500 49995000 9999 2718 10134480 10124482 0.5 16875 49995000 17734631 12306 49995000 9999 4577 17701200 17691204 1 18301 49995000 22551811 13383 49995000 9999 5891 22645149 22635154 ランダム率
課題 181224 この回に実装した整列プログラムは void* の配列を整列するので 通常の int の配列は整列できない そこで バブルソートで int の配列を整列する関数 sortbubble(int*,int,int(*)(int,int)) を実装せよ 実装は Sort.h にプロトタイプ宣言し Sort.cc にコードを追加すること 降順に整列する比較関数を書き 10 個のランダムな整数を降順に並べ替えるテストプログラム TestSort3.cc も示せ 提出方法 : レポートはワードで作成し メールに添付すること ファイル名は scxxxxxx-al181224.docx とすること レポートには学籍番号と氏名を必ず書くこと メールで渕田まで送付すること 提出先 :fuchida@ibe.kagoshima-u.ac.jp メールタイトル : アルゴリズム課題 181224 メール本文にも学籍番号と氏名を必ず書くこと 期限 :2019 年 1 月 6 日 ( 日 ) 24:00
整列アルゴリズムの基礎 終了