与えられた数値の中から最小値を求める処理を考えます。最小値を記憶するために 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
●次のような数字で実際にやってみます。まず、１番〜１０番の中で一番小さいのは12です。これを１番目の52と交換します。
52 46 24 12 15 35 18 56 63 23
12 46 24 52 15 35 18 56 63 23
●１番目を固定し、２番〜１０番の中で最小のものをさがします。それは15です。これを２番目の46と交換します。
12 46 24 52 15 35 18 56 63 23
12 15 24 52 46 35 18 56 63 23
●２番目を固定し、３番〜１０番の中で最小のものをさがします。それは18です。これを３番目の24と交換します。
12 15 24 52 46 35 18 56 63 23
12 15 18 52 46 35 24 56 63 23
●３番目を固定し、４番〜１０番の中で最小のものをさがします。それは24です。これを４番目の52と交換します。
12 15 18 52 46 35 24 56 63 23
12 15 18 23 46 35 24 56 63 52
●これを最後まで繰り返します。最後は９番から１０番の中から最小のものをさがし、９番目と交換することになります。９番目と交換するというのが最後になります。
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
クイックソートは、データを分割してより小さな単位でソートし、あとであわせるという手法をつかって効率を上げています。つまり、
１ データのブロック分割
２ 各ブロックごとの処理（並べ換え）
３ ブロックの統合
という順に作業がすすめられるわけです。速くなるかどうかは１のデータの分割の仕方が工夫のしどころでいろいろなやり方が提案されています。ここで取り上げるのはその中の１つです。。
次のような数字で実際にやってみます。
（１）まず与えられたデータ列の真ん中（左から６番目）に位置する データを基準値として定めます。例では、３５を基準値とします。
52 46 24 12 15 35 18 56 63 23
（２）データを左から順に基準値よりも大きいデータを捜します。まず５２が見つかります。続いて、右から順に基準値よりも小さいデータを捜します。 ２３が見つかります。
52 46 24 12 15 35 18 56 63 23
（３）ここで、５２と２３を入れ替えます。現在注目しているデータの位置を次に進めます（左から見ている場合は一つ右へ、右からの場合は左へ一つ進める）。
23 46 24 12 15 35 18 56 63 52
（４）引き続き左から順に基準値よりも大きいデータを捜します。続きは４６から始まるがすぐ４６が見つかります。続いて、右から順に基準値よりも小さいデータを捜します。 １８が見つかります。
23 46 24 12 15 35 18 56 63 52
（５）４６と１８を交換します。
23 18 24 12 15 35 46 56 63 52
（６）続けて左から基準値より大きいデータを探します。基準値に等しい場合も取り上げることにすると３５そのものに合います。右からも同様に小さいものを探すと３５に合います。これで左右からの捜索がぶつかりました。
ぶつかった所より左は基準値より小さなものが、右は大きいものが集まっています。
23 18 24 12 15 35 46 56 63 52
ここで、２つの部分に分けて、それぞれ（１）からと同様に作業をしていきます。
（７）前半分は１番から５番までです。データ列の真ん中（左から３番目）に位置するデータを基準値として定めます。例では、２４になります。以下同様なのですが、今回は基準値が、たまたまその範囲の最高値になっているのでちょっと面倒です。こんなときでもうまくいきます。
23 18 24 12 15 35 46 56 63 52
（８）データを左から順に基準値(24)よりも大きいデータを捜します。２４です。続いて、右から順に基準値よりも小さいデータを捜します。 １５です。
23 18 24 12 15 35 46 56 63 52
（９）２４と１５を交換します。
23 18 15 12 24 35 46 56 63 52
（10）続けて左側から基準値より大きいものを探します。さっきは２４が３番にありました。今度は４番から探します。すると５番の２４が見つかります。右側からは、基準値より小さいものを探します。さっきは５番に１５がありましたから今度は４番から始めます。すぐ１２が小さいということになります。
23 18 15 12 24 35 46 56 63 52
（11）これで左右からの捜索がぶつかりました。左から来たのは５番の２４まで来ましたし、右からのは４番の１２まできましたから、交差して行き過ぎています。このようなときは交換せず、４番と５番の間でデータを２つに分けます。基準値であった２４よりも小さいものと大きいものに分かれます。右側の２４より大きいのは１つしかありませんが、たまたまこの範囲の最大値だったので仕方ありません。一つしかない要素はこのまま位置が確定します。
23 18 15 12 24 35 46 56 63 52
（12）分かれた１番から４番に対してふたたび(１)からのように、作業をします。繰り返すうち、要素が１つ部分ができては確定してゆきます。前半が終われば後半に進み、ついには全部整列されます。
ある基準値を決めて、それより大きいか小さいかで２つに分け、分かれたものについても同じことを繰り返す。ということです。基準値はデータの大きさで真ん中あたりの数であれば都合がいいのですが、それをじっくり選んでいると時間がかかるので位置で真ん中のものを「えいっ」とつかんで採用するわけです。
原理的にはここまでなのですが、実際にプログラムを組むときには分けるときの境界を含めるか含めないかで迷います。>= を使うか、> を使うかを間違えると、うまく働かないこともありますから、じっくり考えなければならないことになります。
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 |