与えられた数値の中から最小値を求める処理を考えます。最小値を記憶するために min という名前の変数を使います。minの初期値をどうするかはいろいろな考え方がありますがここでは、先頭のデータ data[0]とします。この変数は「仮の最小値」として取り扱われます。
このminと、次のデータの値の比較をします。比較してより小さな値が見つかった場合には、それをminに代入して新しい仮の最小値とします。すべてのデータに対して一通り処理が行われれば、minに記憶されている値が最小値ということになります。
1: /* 最小値を求める k1001.c */ 2: #include <stdio.h> 3: 4: int main() 5: { 6: int data[] = { 52, 46, 24, 12, 15, 35, 18, 56, 63, 23 }; 7: int datanum = 10; 8: int min = data[0]; 9: int i; 10: for( i=1; datanum>i; i++ ) { 11: if( min > data[i] ){ 12: min = data[i]; 13: } 14: } 15: printf( "最小値:%d\n", min ); 16: return 0; 17: }
実行結果はこうなります。
~/c$ ./k1001 最小値: 12
少しの変更で最大値を求めるプログラムになります。最大値の候補をmaxという変数にして次のプログラムを完成させなさい。
1: /* 最大値を求める k1002.c */ 2: #include <stdio.h> 3: 4: int main() 5: { 6: int data[] = { 52, 46, 24, 12, 15, 35, 18, 56, 63, 23 }; 7: int datanum = 10; 8: int max = data[0]; 9: int i; ここを考える 15: printf( "最大値:%d\n", max ); 16: return 0; 17: }
実行結果はこうなるはずです。
~/c$ ./k1002 最大値: 63
データをある規則に従って並べ替えることです。コンピューターの用語では英語で「ソート」とよばれます。ある規則とは数値の大きさの順や文字列のABC順などをさします。
多量のデータを整理するのに欠かせない機能ですからより多くのデータをより速く整列する方法が工夫されました。いまではすでにあるプログラムを利用させてもらうのが一般的です。しかし、整列はプログラミング基礎です。このプログラムの動作を考えることを通してプログラムへの理解が深まります。ぜひ自分がコンピュータになったつもりで考えてみてください。
すべてのデータの中から最も小さい(もしくは大きい)データを選択し,先頭のデータと入れ換える.次に,残りのデータに対して同じ処理を繰り返し,最後から2番目の場所に正しいデータが入ったとき,全体の並べ替えが完了する.このようなやり方を選択ソートといいます。
1: /* 選択ソート */ 2: #include <stdio.h> 3: 4: int main() 5: { 6: int data[] = { 52, 46, 24, 12, 15, 35, 18, 56, 63, 23 }; 7: int datanum = 10; 8: int jn,sonoi,i; 9: for( jn=0; datanum-1>jn; jn++ ) { 10: min = data[jn]; 11: sonoi = jn; 12: for( i=jn+1; datanum>i; i++ ) { 13: if( min > data[i] ){ 14: min = data[i]; 15: sonoi = i; 16: } 17: } 18: data[sonoi] = data[jn]; 19: data[jn] = min; 20: } 21: for ( i=0; datanum>i; i++) { 22: printf( "%d ",data[i] ); 23: } 24: printf("\n"); 25: return 0; 26: }
これが標準的な最小値選択方式の並べ替えで選択ソートとよばれる種類の典型的な例です。 「範囲の中で最小なものを選択して範囲の一番端のものと交換し,範囲を狭める」ということを繰り返しています。
「検索する単語を入力してください」に「you」と入れると、実行結果はこうなります。
~/c$ ./k1003 12 15 18 23 24 35 46 52 56 63
●次のような数字で実際にやってみます。まず、1番〜10番の中で一番小さいのは12です。これを1番目の52と交換します。
52 46 24 12 15 35 18 56 63 23
12 46 24 52 15 35 18 56 63 23
●1番目を固定し、2番〜10番の中で最小のものをさがします。それは15です。これを2番目の46と交換します。
12 46 24 52 15 35 18 56 63 23
12 15 24 52 46 35 18 56 63 23
●2番目を固定し、3番〜10番の中で最小のものをさがします。それは18です。これを3番目の24と交換します。
12 15 24 52 46 35 18 56 63 23
12 15 18 52 46 35 24 56 63 23
●3番目を固定し、4番〜10番の中で最小のものをさがします。それは24です。これを4番目の52と交換します。
12 15 18 52 46 35 24 56 63 23
12 15 18 23 46 35 24 56 63 52
●これを最後まで繰り返します。最後は9番から10番の中から最小のものをさがし、9番目と交換することになります。9番目と交換するというのが最後になります。
12 15 18 23 24 35 46 52 63 56
12 15 18 23 24 35 46 52 56 63
整列方法を挿入法に替えてやってみます。(Binary Search)
1: /* 挿入ソート */ 2: #include <stdio.h> 3: 4: int main() 5: { 6: int data[] = { 52, 46, 24, 12, 15, 35, 18, 56, 63, 23 }; 7: int datanum = 10; 8: int tmp,i,p,j; 9: for( i=1; datanum>i; i++ ) { 10: int tmp = data[i]; 11: p=i; 12: while( p>0 && data[p-1]>tmp ){ 13: data[p] = data[p-1]; 14: p--; 15: } 16: data[p] = tmp; 17: } 18: for ( i=0; datanum>i; i++) { 19: printf( "%d ",data[i] ); 20: } 21: printf("\n"); 22: return 0; 23: }
実行結果は
12 15 18 23 24 35 46 52 56 63
46 52 24 12 15 35 18 56 63 23 24 46 52 12 15 35 18 56 63 23 12 24 46 52 15 35 18 56 63 23
12 15 24 46 52 35 18 56 63 23
12 15 24 35 46 52 18 56 63 23
12 15 18 24 35 46 52 56 63 23 12 15 18 24 35 46 52 56 63 23 12 15 18 24 35 46 52 56 63 23 12 15 18 23 24 35 46 52 56 63
1: /* クイックソート */ 2: #include <stdio.h> 3: 4: void qksort(int a[],int bgn,int end) 5: { 6: int sm = bgn; 7: int bg = end; 8: int i = (sm+bg)/2; 9: int kjn= a[i]; /*これが基準値*/ 10: int tmp; 11: 12: while(1){ 13: while ( kjn > a[sm] ){ sm++; } /*左から大きいものを検索*/ 14: while ( a[bg] > kjn ){ bg--; } /*右から小さいものを検索*/ 15: if ( sm > bg ){ break; } /* 無限ループから抜ける */ 16: tmp=a[sm]; 17: a[sm]=a[bg]; 18: a[bg]=tmp; 19: sm++; 20: bg--; 21: } 22: 23: if (bg > bgn) {qksort(a,bgn,bg);} /*前半を指定して再帰呼び出し*/ 24: if (end > sm) {qksort(a,sm,end);} /*後半を指定して再帰呼び出し*/ 25: } 26: 27: int main() 28: { 29: int data[] = { 52, 46, 24, 12, 15, 35, 18, 56, 63, 23 }; 30: int datanum = 10; 31: qksort(data,0,datanum-1); 32: int i; 33: for ( i=0; datanum>i; i++) { 34: printf( "%d ",data[i] ); 35: } 36: printf("\n"); 37: }
実行結果はもちろん
~/c$ ./k1005 12 15 18 23 24 35 46 52 56 63
クイックソートは、データを分割してより小さな単位でソートし、あとであわせるという手法をつかって効率を上げています。つまり、
1 データのブロック分割 2 各ブロックごとの処理(並べ換え) 3 ブロックの統合
という順に作業がすすめられるわけです。速くなるかどうかは1のデータの分割の仕方が工夫のしどころでいろいろなやり方が提案されています。ここで取り上げるのはその中の1つです。。
次のような数字で実際にやってみます。
(1)まず与えられたデータ列の真ん中(左から6番目)に位置する データを基準値として定めます。例では、35を基準値とします。
52 46 24 12 15 35 18 56 63 23
(2)データを左から順に基準値よりも大きいデータを捜します。まず52が見つかります。続いて、右から順に基準値よりも小さいデータを捜します。 23が見つかります。
52 46 24 12 15 35 18 56 63 23
(3)ここで、52と23を入れ替えます。現在注目しているデータの位置を次に進めます(左から見ている場合は一つ右へ、右からの場合は左へ一つ進める)。
23 46 24 12 15 35 18 56 63 52
(4)引き続き左から順に基準値よりも大きいデータを捜します。続きは46から始まるがすぐ46が見つかります。続いて、右から順に基準値よりも小さいデータを捜します。 18が見つかります。
23 46 24 12 15 35 18 56 63 52
(5)46と18を交換します。
23 18 24 12 15 35 46 56 63 52
(6)続けて左から基準値より大きいデータを探します。基準値に等しい場合も取り上げることにすると35そのものに合います。右からも同様に小さいものを探すと35に合います。これで左右からの捜索がぶつかりました。
ぶつかった所より左は基準値より小さなものが、右は大きいものが集まっています。
23 18 24 12 15 35 46 56 63 52
ここで、2つの部分に分けて、それぞれ(1)からと同様に作業をしていきます。
(7)前半分は1番から5番までです。データ列の真ん中(左から3番目)に位置するデータを基準値として定めます。例では、24になります。以下同様なのですが、今回は基準値が、たまたまその範囲の最高値になっているのでちょっと面倒です。こんなときでもうまくいきます。
23 18 24 12 15 35 46 56 63 52
(8)データを左から順に基準値(24)よりも大きいデータを捜します。24です。続いて、右から順に基準値よりも小さいデータを捜します。 15です。
23 18 24 12 15 35 46 56 63 52
(9)24と15を交換します。
23 18 15 12 24 35 46 56 63 52
(10)続けて左側から基準値より大きいものを探します。さっきは24が3番にありました。今度は4番から探します。すると5番の24が見つかります。右側からは、基準値より小さいものを探します。さっきは5番に15がありましたから今度は4番から始めます。すぐ12が小さいということになります。
23 18 15 12 24 35 46 56 63 52
(11)これで左右からの捜索がぶつかりました。左から来たのは5番の24まで来ましたし、右からのは4番の12まできましたから、交差して行き過ぎています。このようなときは交換せず、4番と5番の間でデータを2つに分けます。基準値であった24よりも小さいものと大きいものに分かれます。右側の24より大きいのは1つしかありませんが、たまたまこの範囲の最大値だったので仕方ありません。一つしかない要素はこのまま位置が確定します。
23 18 15 12 24 35 46 56 63 52
(12)分かれた1番から4番に対してふたたび(1)からのように、作業をします。繰り返すうち、要素が1つ部分ができては確定してゆきます。前半が終われば後半に進み、ついには全部整列されます。
ある基準値を決めて、それより大きいか小さいかで2つに分け、分かれたものについても同じことを繰り返す。ということです。基準値はデータの大きさで真ん中あたりの数であれば都合がいいのですが、それをじっくり選んでいると時間がかかるので位置で真ん中のものを「えいっ」とつかんで採用するわけです。
原理的にはここまでなのですが、実際にプログラムを組むときには分けるときの境界を含めるか含めないかで迷います。>= を使うか、> を使うかを間違えると、うまく働かないこともありますから、じっくり考えなければならないことになります。
k1003.c に数える部分を書き加えます。clockに関する部分はなくてもよい。
1: /* 選択ソートの手間を数える */ 2: #include <stdio.h> 3: #include <stdlib.h> 4: #include <time.h> 5: #define DATANUM 100 6: int disp(int data[],int st, int ed) 7: { 8: int n; 9: for ( n=st; ed>n; n++) { 10: printf( "%4d ",data[n] ); 11: } 12: printf("\n"); 13: return 0; 14: } 15: 16: int main() 17: { 18: int jn,sonoi,i,min; 19: int ctcpy=0; 20: int ctcmp=0; 21: clock_t start, end; /*時刻計測*/ 22: srand( (unsigned int)time( NULL ) ); /*乱数初期化*/ 23: int data[DATANUM]; 24: int datanum = DATANUM; 25: for (i=0 ;datanum>i ;i++){ 26: data[i] = rand()%10000; 27: } 28: disp(data,0,10); /*最初の10個を表示*/ 29: disp(data,datanum-10,datanum); /*最後の10個を表示*/ 30: start = clock(); /*時刻計測*/ 31: min = data[0]; 32: ctcpy++; 33: ctcpy++; 34: for( jn=0; datanum-1>jn; jn++ ) { 35: ctcmp++; 36: ctcpy++; 37: min = data[jn]; 38: ctcpy++; 39: sonoi = jn; 40: ctcpy++; 41: ctcpy++; 42: for( i=jn+1; datanum>i; i++ ) { 43: ctcmp++; 44: ctcpy++; 45: if( min > data[i] ){ 46: ctcmp++; 47: min = data[i]; 48: ctcpy++; 49: sonoi = i; 50: ctcpy++; 51: } 52: } 53: data[sonoi] = data[jn]; 54: ctcpy++; 55: data[jn] = min; 56: ctcpy++; 57: } 58: end = clock(); /*時刻計測*/ 59: disp(data,0,10); /*最初の10個を表示*/ 60: disp(data,datanum-10,datanum); /*最後の10個を表示*/ 61: printf("比較回数:%d 代入回数:%d\n",ctcmp,ctcpy); 62: printf("%.4f秒かかりました\n",(double)(end-start)/CLOCKS_PER_SEC); 63: return 0; 64: }
k1006 実行結果は
~/c$ ./k1006 4447 8857 1827 2649 5944 2085 380 4922 2442 6493 4459 4937 8498 4369 4666 5115 8813 7264 8315 2301 0 0 0 1 1 1 2 3 3 5 9994 9995 9996 9996 9996 9998 9998 9999 9999 9999 比較回数:50081551 代入回数:50208100 0.2300秒かかりました
k1004.c に数える部分を書き加えます。clockに関する部分はなくてもよい。
1: /* 挿入ソート の手間を数える*/ 2: #include <stdio.h> 3: #include <stdlib.h> 4: #include <time.h> 5: #define DATANUM 100 6: int disp(int data[],int st, int ed) 7: { 8: int n; 9: for ( n=st; ed>n; n++) { 10: printf( "%4d ",data[n] ); 11: } 12: printf("\n"); 13: return 0; 14: } 15: 16: int main() 17: { 18: int tmp,i,p,j,min; 19: clock_t start, end; /*時刻計測*/ 20: srand( (unsigned int)time( NULL ) ); /*乱数初期化*/ 21: int data[DATANUM]; 22: int datanum = DATANUM; 23: for (i=0 ;datanum>i ;i++){ 24: data[i] = rand()%10000; 25: } 26: disp(data,0,10); /*最初の10個を表示*/ 27: disp(data,datanum-10,datanum); /*最後の10個を表示*/ 28: start = clock(); /*時刻計測*/ 29: int ctcpy=0; 30: int ctcmp=0; 31: ctcpy++; 32: for( i=1; datanum>i; i++ ) { 33: ctcmp++; 34: ctcpy++; 35: int tmp = data[i]; 36: ctcpy++; 37: p=i; 38: ctcpy++; 39: while( p>0 && data[p-1]>tmp ){ 40: ctcmp++; 41: ctcmp++; 42: data[p] = data[p-1]; 43: ctcpy++; 44: p--; 45: ctcpy++; 46: } 47: data[p] = tmp; 48: ctcpy++; 49: } 50: end = clock(); /*時刻計測*/ 51: disp(data,0,10); /*最初の10個を表示*/ 52: disp(data,datanum-10,datanum); /*最後の10個を表示*/ 53: printf("比較回数:%d 代入回数:%d\n",ctcmp,ctcpy); 54: printf("%.4f秒かかりました\n",(double)(end-start)/CLOCKS_PER_SEC); 55: return 0; 56: }
k1007.c 実行結果は
~/c$ ./k1007 6537 4102 7919 9347 6194 9998 7324 9847 7613 906 4169 6070 8073 4933 8137 5650 7124 807 620 5098 1 1 2 3 3 5 6 6 9 10 9991 9991 9993 9994 9997 9997 9998 9998 9998 9998 比較回数:50171405 代入回数:50201403 0.1700秒かかりました
k1005.c に数える部分を書き加えます。clockに関する部分はなくてもよい。
1: /* クイックソートの手間を数える */ 2: #include <stdio.h> 3: #include <stdlib.h> 4: #include <time.h> 5: #define DATANUM 10000 6: int ctcpy=0; 7: int ctcmp=0; 8: 9: int disp(int data[],int st, int ed) 10: { 11: int n; 12: for ( n=st; ed>n; n++) { 13: printf( "%4d ",data[n] ); 14: } 15: printf("\n"); 16: return 0; 17: } 18: 19: void qksort(int a[],int bgn,int end) 20: { 21: int sm = bgn; 22: int bg = end; 23: int i = (sm+bg)/2; 24: int kjn= a[i]; /*これが基準値*/ 25: int tmp; 26: 27: while(1){ 28: while ( kjn > a[sm] ){ sm++;ctcpy++;} /*左から大きいものを検索*/ 29: ctcmp++; 30: while ( a[bg] > kjn ){ bg--;ctcpy++;} /*右から小さいものを検索*/ 31: ctcmp++; 32: if ( sm > bg ){ break; } /* 無限ループから抜ける */ 33: ctcmp++; 34: tmp=a[sm]; 35: ctcpy++; 36: a[sm]=a[bg]; 37: ctcpy++; 38: a[bg]=tmp; 39: ctcpy++; 40: sm++; 41: ctcpy++; 42: bg--; 43: ctcpy++; 44: } 45: 46: if (bg > bgn) {qksort(a,bgn,bg);} /*前半を指定して再帰呼び出し*/ 47: ctcmp++; 48: if (end > sm) {qksort(a,sm,end);} /*後半を指定して再帰呼び出し*/ 49: ctcmp++; 50: } 51: 52: int main() 53: { 54: clock_t start, end; /*時刻計測*/ 55: srand( (unsigned int)time( NULL ) ); /*乱数初期化*/ 56: int data[DATANUM]; 57: int datanum = DATANUM; 58: int i; 59: for (i=0 ;datanum>i ;i++){ 60: data[i] = rand()%10000; 61: } 62: disp(data,0,10); /*最初の10個を表示*/ 63: disp(data,datanum-10,datanum); /*最後の10個を表示*/ 64: start = clock(); /*時刻計測*/ 65: 66: qksort(data,0,datanum-1); 67: 68: end = clock(); /*時刻計測*/ 69: disp(data,0,10); /*最初の10個を表示*/ 70: disp(data,datanum-10,datanum); /*最後の10個を表示*/ 71: printf("比較回数:%d 代入回数:%d\n",ctcmp,ctcpy); 72: printf("%.4f秒かかりました\n",(double)(end-start)/CLOCKS_PER_SEC); 73: return 0; 74: }
k1008.c 実行結果は
~/c$ ./k1008 4324 2324 505 4681 143 7577 836 8603 2001 6297 9647 5891 9100 5488 860 7574 9172 8606 7868 2704 0 1 2 3 5 6 6 7 7 8 9990 9990 9992 9992 9992 9993 9994 9997 9999 9999 比較回数:137684 代入回数:311270 0.0000秒かかりました
データ数 | 選択ソート | 挿入ソート | クイックソート | ||||||
---|---|---|---|---|---|---|---|---|---|
比較回数 | 代入回数 | 時間 | 比較回数 | 代入回数 | 時間 | 比較回数 | 代入回数 | 時間 | |
100 | 5346 | 6140 | 0.00 | 4781 | 5079 | 0.00 | 865 | 1688 | 0.00 |
1000 | 505735 | 515968 | 0.00 | 509105 | 512103 | 0.00 | 11386 | 24391 | 0.00 |
10000 | 50081551 | 50208100 | 0.23 | 50171405 | 50201403 | 0.17 | 137713 | 312011 | 0.00 |