|
|
例題 2
5 個の整数を順に読み込み，配列 a に格納しなさい．
そして，それらを昇順（小さい順）に並び替えて表示しなさい．
方針・アルゴリズム
まず，
例題1
と同様にして，
a[0], ..., a[4] の中の最大値 a[m] を見つけ出す．
そして，その最大値 a[m] と a[4] の値を入れ替える．
例えば，
| a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
| 8 |
-2 |
91 |
0 |
1 |
であったとすると，最大値は a[2] ということになるので，
これを右端の a[4] と交換する．
| a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
| 8 |
-2 |
1 |
0 |
91 |
次に
1 個だけ範囲を狭め，
a[0], ..., a[3]
の範囲で最大値を見つけ出す．
| a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
| 8 |
-2 |
1 |
0 |
91 |
そして同様に右端（a[3]）と交換する．
| a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
| 0 |
-2 |
1 |
8 |
91 |
ここまでで最大値が右端に，その次に大きい値がその隣に，
という具合いに並び替えられた．
後は右端が a[1] になるまで同様の手順を繰り返していけばよい．
この手法（アルゴリズム）を
選択ソート（selection sort）
という．
- n = 4 〜 1 の範囲（-1
していく）で以下を繰り返す（右端をずらす）：
- m = 0 と仮定（ a[0] が最大値と仮定）する．
- そして，i の値を 1 〜 n の範囲で変化させながら，
a[m] < a[i] ならば m ← i とする．
（※ a[i] の方が大きいので，
改めてそちらを最大値として仮定するという意味）
- 最後に m < n なら a[m] と a[n] の値を交換する．
コーディング例
1 /*
2 * プログラミング演習 第 12 回
3 * [例題 2]
4 * (C) 2006 Hirohisa AMAN <aman@cs.ehime-u.ac.jp, aman@computer.org>
5 */
6 #include <stdio.h>
7
8 int main(void){
9 int i, n, m, a[5], tmp;
10
11 /* a[i] を読み込む */
12 for ( i = 0; i < 5; i++ ){
13 scanf("%d", &a[i]);
14 }
15
16 for ( n = 4; n >= 0; n-- ){
17 m = 0; /* a[0] を最大値と仮定 */
18 for ( i = 1; i <= n; i++ ){
19 if ( a[m] < a[i] ){
20 m = i; /* 最大値の位置の更新 */
21 }
22 }
23 if ( m < n ){ /* a[m] と a[n] の値を交換 */
24 tmp = a[m];
25 a[m] = a[n];
26 a[n] = tmp;
27 }
28 }
29
30 for ( i = 0; i < 5; i++ ){
31 printf("%d ", a[i]);
32 }
33 printf("\n");
34
35 return 0;
36 }
※左端の数字は行番号であり，ソースコードには含まれない点に注意！
コンパイル & 実行例
$ gcc example12_2.c [Enter]
$ ./a.out [Enter]
8 -2 91 0 1 [Enter]
-2 1 0 8 91
|
