最小値と整列

課題10-1 最小値を求める

与えられた数値の中から最小値を求める処理を考えます。最小値を記憶するために min という名前の変数を使います。minの初期値をどうするかはいろいろな考え方がありますがここでは、先頭のデータ data[0]とします。この変数は「仮の最小値」として取り扱われます。

このminと、次のデータの値の比較をします。比較してより小さな値が見つかった場合には、それをminに代入して新しい仮の最小値とします。すべてのデータに対して一通り処理が行われれば、minに記憶されている値が最小値ということになります。

プログラム名 k1001.c

 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: }

実行結果 k1001.c

実行結果はこうなります。

~/c$ ./k1001
最小値: 12

課題10-2 最大値

少しの変更で最大値を求めるプログラムになります。最大値の候補をmaxという変数にして次のプログラムを完成させなさい。

プログラム名 k1002.c

 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: }

実行結果 k1002.c

実行結果はこうなるはずです。

~/c$ ./k1002
最大値: 63

整列(ソート)

データをある規則に従って並べ替えることです。コンピューターの用語では英語で「ソート」とよばれます。ある規則とは数値の大きさの順や文字列のABC順などをさします。

多量のデータを整理するのに欠かせない機能ですからより多くのデータをより速く整列する方法が工夫されました。いまではすでにあるプログラムを利用させてもらうのが一般的です。しかし、整列はプログラミング基礎です。このプログラムの動作を考えることを通してプログラムへの理解が深まります。ぜひ自分がコンピュータになったつもりで考えてみてください。

課題10-3 選択ソート

すべてのデータの中から最も小さい(もしくは大きい)データを選択し,先頭のデータと入れ換える.次に,残りのデータに対して同じ処理を繰り返し,最後から2番目の場所に正しいデータが入ったとき,全体の並べ替えが完了する.このようなやり方を選択ソートといいます。

プログラム名 k1003.c

 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: }

これが標準的な最小値選択方式の並べ替えで選択ソートとよばれる種類の典型的な例です。 「範囲の中で最小なものを選択して範囲の一番端のものと交換し,範囲を狭める」ということを繰り返しています。

実行結果 k1003.c

「検索する単語を入力してください」に「you」と入れると、実行結果はこうなります。

~/c$ ./k1003
12 15 18 23 24 35 46 52 56 63 

k1003の考え方

次のような数字で実際にやってみます。まず、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 

課題10-4 挿入ソート

整列方法を挿入法に替えてやってみます。(Binary Search)

プログラム名 k1004.c

 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: }

実行結果 k1004.c

実行結果は

12 15 18 23 24 35 46 52 56 63 

k1004の考え方

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

課題10-5 クイックソート

プログラム名 k1005.c

 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

k1005の考え方

クイックソートは、データを分割してより小さな単位でソートし、あとであわせるという手法をつかって効率を上げています。つまり、

        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つに分け、分かれたものについても同じことを繰り返す。ということです。基準値はデータの大きさで真ん中あたりの数であれば都合がいいのですが、それをじっくり選んでいると時間がかかるので位置で真ん中のものを「えいっ」とつかんで採用するわけです。

原理的にはここまでなのですが、実際にプログラムを組むときには分けるときの境界を含めるか含めないかで迷います。>= を使うか、> を使うかを間違えると、うまく働かないこともありますから、じっくり考えなければならないことになります。

課題10-6 選択ソートの手間を数える

k1003.c に数える部分を書き加えます。clockに関する部分はなくてもよい。

プログラム名 k1006.c

 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秒かかりました

課題10-7 挿入ソートの手間を数える

k1004.c に数える部分を書き加えます。clockに関する部分はなくてもよい。

プログラム名 k1007.c

 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秒かかりました

課題10-8 クイックソートの手間を数える

k1005.c に数える部分を書き加えます。clockに関する部分はなくてもよい。

プログラム名 k1008.c

 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 534661400.00 478150790.00 86516880.00
1000 5057355159680.00 5091055121030.00 11386243910.00
10000 50081551502081000.23 50171405502014030.17 1377133120110.00

手間のグラフ

聖愛中学高等学校
http://www.seiai.ed.jp/
Jan. 2012