10 （6/30）反復；for文

10.1 はじめに

10.1.1 グループ発表（10分）；前回の復習

なし

10.1.2

・繰り返しのアルゴリズム；For文

・2重For文

10.2 本題

10.2.1 反復；For文

アルゴリズムの基本3要素；順次，選択（分岐），繰り返し（反復）

List6-1とList6-2

for ( i = 0 ; i < 3 ; i++ ) {
  printf("i= %d\n", i);
}

for ( ループ（制御変数）の初期化 ; ループの条件（偽になったらループ終了） ;  ループ（制御変数）の変化 ) {
  ループで繰り返す処理;
}

• 
• For文では，まず条件を調べて，それから繰り返しの処理に移る．
• 次の一歩（制御変数の変化）は，繰り返し処理の後に実行．

Fig. 6-2の説明

10.2.2 クイズ

10.2.3 バリエーション

List6-3

2重ループ；List6-4

10.2.4 間違い探し

10.2.5 main関数の引数(argc, argv[])

読解練習「引数表示プログラム」(arg.c)

10.3 If文とForループの使用例；ソート（整列）

If文とForループを使うプログラムの例として，数字の並び替え問題を取り上げます．受験生の成績を大きい順番に並び替えたり，出席カードを番号順に並び替えたりといった数字の整列は，日常生活でも頻繁に行われる作業です．並び替えなければいけないデータ数が億の単位になることも珍しくありません．データ数が多くなると，上手に並び替えてやらないとなかなか処理が終わりません．というわけで，いろいろな並び替え方，すなわち整列のアルゴリズムが考案されてきました．ここではもっとも単純な（しかし時間がかかる）方法であるアルゴリズムとして，単純選択ソートを紹介します．

10.3.1 単純選択ソート

これは非常にわかりやすい方法です．たとえば，（5，3，8，1）という4つのデータを並び替える場合は以下のように処理します．

1. 4つの中から一番小さいデータを探します．4番目の1が最小値なので1番目のデータの5と交換します．
2. 並び替えの結果，（1，3，8，5）となりました．
3. 今度は残り3つの中から一番小さいデータを探します．2番目の3が最小値なので，2番目のデータと交換します．
4. 並び替えの結果，（1，3，8，5）となりました．
5. 残り2つの中から一番小さいデータを探します．4番目の5が最小値なので，3番目のデータと交換します．
6. 並び替えの結果，（1，3，5，8）となりました．
7. これでお終い．

この解法をもう少しプログラム風に書き直します．データはdata[]という名前の配列に入っているとします．すなわち，data[] = {5, 3, 8, 1}です．別々に書けば，data[0]=5, data[1]=3, data[2]=8, data[3]=1です．

1. 最小値を探してdata[0]に移動させます．そのためにまずdata[0]とdata[1]からdata[3]までの3つのデータを比較して一番小さいデータを探します．次に一番小さいデータとdata[0]のデータを交換してdata[0]に一番小さいデータを入れます．今の場合はdata[0]とdata[3]を交換します．
2. 並び替えの結果，data[]= {1, 3, 8, 5}となりました．
3. 今度は残り3つの中の最小値をdata[1]に移動させます．そのためにまずdata[1]とdata[2]からdata[3]までの2つのデータを比較してその中で一番小さいデータを探します．次に見つけたデータとdata[1]のデータを交換してdata[1]にこのデータを入れます．今の場合はdata[1]の方がdata[2]よりもdata[3]よりも小さいので順番は変わりません．
4. 並び替えの結果，data[]= {1, 3, 8, 5}となりました．
5. 以下同様です．今度は残り2つの中の最小値，つまり3番目に小さいデータ，をdata[2]に移動させます．そのためにまずdata[2]とdata[3]を比較して小さいほうのデータの場所を探します．次に小さい方のデータをdata[2]に移動してお互いの場所を交換します．今の場合はdata[2]とdata[3]を交換します．
6. 並び替えの結果，data[]= {1, 3, 5, 8}となりました．
7. これでお終い．

では実際にプログラム(sort.c)を書いてみます．

• 変数iは大きなForループの制御変数（カウンタ）で，何番目の最小値を探しているかを示します．0番目の最小値，つまり一番小さい値，をdata[0]に移動させます．データの数はn個ですが，データの場所は0から(n-1)までです．最後の1個，つまり一番大きな値，は自動的に決まるので，iは0から(n-2)までループすれば十分です．
• 変数iは2番目のForループのカウンタで，小さい方の値を探すために使われます．上の説明からわかるように，このカウンタは(i+1)番目のデータから(n-1)番目のデータを示して，各場所のデータとi番目のデータの値をif文で比較します．
• 変数min_iには小さい方のデータの場所が入ります．2番目のループが終了したときには，ループの範囲の中で一番小さいデータの場所がこの変数に入っています．
• 変数min_dataには一番小さいデータの値，つまりdata[min_i]が入ります．
• 変数data[]は，整列対象となる数字が入っている配列です．
• 変数nはデータの個数です．

このソースのように，変数にその役割を示す名前をつけたり，変数や文の意味をコメントで書いておいたり，適所にprintf文を入れてプログラム内部の様子（Forループのカウンタの値や大事な変数の値）を表示させたりすることで，プログラムが何をやっているのかがわかりやすくなります．コメントなどの注釈がないプログラムの例(sort_0.c)と見比べてみてください．

このプログラムの実行結果を示します．

nabe@gaia:~/compB% ./sort

整列前のデータ: data[]= 5, 3, 8, 1

0番目の初期値を探す ***************************************************
     データ比較のForループ1回目（If文  成立 ）: 現在の最小データの場所=1
     データ比較のForループ2回目（If文 不成立）:
     データ比較のForループ3回目（If文  成立 ）: 現在の最小データの場所=3
** データの入れ替え: 0番目のデータと3番目のデータを入れ替えました
** 入れ替え後のデータ: data[]= 1, 3, 8, 5

1番目の初期値を探す ***************************************************
     データ比較のForループ2回目（If文 不成立）:
     データ比較のForループ3回目（If文 不成立）:
** データの入れ替え: 1番目のデータと1番目のデータを入れ替えました
** 入れ替え後のデータ: data[]= 1, 3, 8, 5

2番目の初期値を探す ***************************************************
     データ比較のForループ3回目（If文  成立 ）: 現在の最小データの場所=3
** データの入れ替え: 2番目のデータと3番目のデータを入れ替えました
** 入れ替え後のデータ: data[]= 1, 3, 5, 8

整列後のデータ: data[]= 1, 3, 5, 8

もう少しデータ数を増やしてみました．「単純選択ソートその２」(sort2.c)

10.4 おわりに

10.4.1 課題

• 「sort_0.c」を説明できるようにする．sort_0.cにコメントを入れたり，わかりやすい変数名に変えたり，ループの途中経過やif文が成立したかどうかをprint文で表示したりしてみる．来週のグループ発表で，sort_0.cを説明してもらいます．
• 6章の間違い探し
• 練習問題6-1

10.4.2 次回までに打ち込んで実行しておくプログラム

List7-1，List7-2，List7-3，List7-4，List7-5

10.4.3 次回の学習目標

・アルゴリズムを考えてからプログラミング

・6章までの範囲でプログラミング演習

・While文

10.4.4 コメントカード