(45.1) 挿入ソートは、次に学ぶ Shell ソートの基礎になる。 次の二つを利用して配列をソートするものである。
| 48 | -- | -- | -- | -- | -- | -- |
| 03 | 05 | 48 | 92 | 13 | -- | -- |
| ↓ | ||||||
| 03 | 05 | 13 | 48 | 92 | -- | -- |
(45.2) 図書カード --- 数学教室図書室にもあるような、図書室で蔵書を検索する際に使うカード --- が（たとえば）著者名順に並んでいるところへ、 新しく到着した図書のカードを追加するときは、 まさにこの二段目を行なうことになるだろう。 すなわち、すでに並んでいるカードを新しいカードがはいるべきところで二組に分け、 そこに新しいカードを挿入することになる。
(45.3) 図書カードのときは、 新しく挿入したカードよりも「大」なるカードはカード一枚の厚みの分だけ奥にずれる。 しかし、コンピュータではそう簡単にはいかないので、次のような操作を行なう。
(45.4) つまり、二段目の各ステップは
(45.5) 上の例ではこうなる。
| 03 | 05 | 48 | 92 | 13 | -- | -- |
| ↓ | ||||||
| 03 | 05 | 48 | 13 | 92 | -- | -- |
| ↓ | ||||||
| 03 | 05 | 13 | 48 | 92 | -- | -- |
(45.6) プログラムでは、 「j > 1 かつ a[j-1] > a[j] である限り」 と考え、for ループを使うとよいだろう。 「かつ」はＣ言語では && と書くのだった。
(45.7) そして、これを、i が 2 から N まで、 i の値を一つずつ大きくしながら行なってゆく。
(45.8) 初めからソートされていた場合が最も lucky な場合であり、 そのときの比較回数は N-1, 交換回数は 0 である。 逆順にソートされていた場合が最悪の場合であり、 このときはどちらもおよそ N2/2 となる。 平均的な場合には、 a[i] を挿入するときの比較・交換回数はどちらもおよそ i/2 であろう。 よって、全体では比較・交換回数とも N2/4 とみてよいだろう。 どちらもΟ(N2) である。 前の二つのアルゴリズムと異なり、 もしも配列がほとんどソートされていれば比較回数も交換回数も小さいことに注意。
(46.1) 前からの準備を元にして、 乱数列で初期化された配列を挿入ソートでソートするプログラムを書け。 また、配列の大きさと比較回数・交換回数との関係を調べよ。 そして、メールでレポートせよ。
#include ...
main() {
...
for (i = ?; i <= ?; i++) {
printf("いまから a[%d] を挿入します.\n", i);
for (j = ?; j ???; j??) {
...
swap(?, ?);
print();
}
}
}
#include ...
int ccount = 0; /* 比較（comp()）のカウンタ。0 で初期化 */
int scount = 0; /* 交換（swap()）のカウンタ。0 で初期化 */
main() {
int i, j;
printf("配列の大きさは %d です.\n", N); /* 配列の大きさを出力 */
init();
/* ここでソートを行なう */
printf("%d 回比較しました.\n", ccount); /* 比較回数を出力 */
printf("%d 回交換しました.\n", scount); /* 交換回数を出力 */
}
void swap(int i, int j) {
...
scount++; /* ここを通るたびにカウンタが増える */
}
int comp(int i, int j) {
ccount++; /* ここを通るたびにカウンタが増える */
return a[i] - a[j];
}
（このときの出力は
配列の大きさは .... です. 乱数の種は .......... です. ...... 回比較しました. ...... 回交換しました.のみとなる。）
(46.2) ※ コメント「配列の大きさを出力」 をつけた行を main() の冒頭に入れておくと、 出力結果を見るだけで配列の大きさがわかり、便利である。
(46.3) レポートには、まず、完成したプログラムを載せること。 その際、Active! mail のメール作成画面の「添付ファイル」 *ではなく* 本文の中にソースファイルを貼りつけること。 また、プログラムはそのままコンパイルできる状態のものでなければならない。 （たとえば
#define N /* ここに配列の大きさを入れてコンパイルしてください */と書いて送られるとこのままではコンパイルできず、 採点に時間がかかるからやめるように、という意味である。
(46.4) 比較回数・交換回数を調べる際には、 配列の大きさ N の値を最低でも三通りに変えること。 N の値があまり小さいと意味がないし、 大きすぎると実行に時間がかかりすぎる。 適当な範囲でなるべく大きいほうがよいし、 あまり近くない数を選ぶほうがよい。 1:10:100 とするのも一つの方法である。 それぞれの N について最低でも５回ずつくり返して実験せよ。 その際、乱数の種が毎回異なるようにするため、 一秒以内に二度以上プログラムを動かすな。 この実験結果は
[z08ec0??@ipe???? ~]$ ./a.out
配列の大きさは ????? です.
乱数の種は ?????????? です.
???????? 回比較しました.
???????? 回交換しました.
[z08ec0??@ipe???? ~]$ ./a.out
配列の大きさは ????? です.
乱数の種は ?????????? です.
???????? 回比較しました.
???????? 回交換しました.
....
[z08ec0??@ipe???? ~]$ ./a.out
配列の大きさは ????? です.
乱数の種は ?????????? です.
???????? 回比較しました.
???????? 回交換しました.
[z08ec0??@ipe???? ~]$
のようになるだろう。全部をまとめてコピー&ペーストして構わない。
すなわち、プロンプトや ./a.out がレポートにはいっていてもよい。
(46.5) N の値は三通りに変えるが、 提出するプログラムはそのうちの一つでよい。 ただし、実験を行なったプログラムそのものでなければならない。
(46.6) 感想など、上で書くよう指示したこと以外のものは書かなくてよい。 （書きたければ書いてもよい。）
(46.7) 宛て先は私（岩瀬）の実習用アカウント（(34.6) 参照）です。 件名は「kadai3」（←全て半角文字、アルファベットは小文字、 途中にスペースをいれない）としてください。 自分の学籍番号、氏名（として大学に届けてあるもの） をメールの *本文内にも* 書くのを忘れずに。 締め切りは、諸君の進みぐあいを見たうえで決め、 この実習の最初のページに発表します。
(47.1) ここは、時間などに余裕がある人のためのオプション項目である。
(47.2) 配列 a[ ] を初期化する際、わざと偏ったやり方で行なったら、 比較回数や交換回数はどうなるだろうか？ 「a[i] = i;」と書けば元々データはソートされていたことになる。 「a[i] = N + 1 - i;」なら逆順。 「a[i] = i + rand() % 5;」とすれば 「だいたいそろっているが完全にソートされていないデータ」になる。 （5 という数に特別な意味はない。）
(48.1) ここは、時間などに余裕がある人のためのオプション項目である。
(48.2) 本当にソートできたかどうかチェックするルーチンをつけてみよう。 配列 a[ ] に 0 が代入されていないこと、および、 a[1] が a[2] 以下であること、 a[2] が a[3] 以下であること、 ………、 a[N-1] が a[N] 以下であること、 を順にチェックすればよい。 違っていたらメッセージを画面に出力させる。
(48.3) 独立した関数にしてもよいし、 main() の最後に置いてもよいだろう。