(6.1.1) 挿入ソートは，次の原理で配列をソートする。 あとで学ぶ Shell ソートの基礎となる。
| 48 | -- | -- | -- | -- | -- | -- |
| 03 | 05 | 48 | 92 | 13 | -- | -- |
| ↓ | ||||||
| 03 | 05 | 13 | 48 | 92 | -- | -- |
(6.1.2) 図書カード --- 数学教室図書室にもあるような，図書室で蔵書を検索する際に使うカード --- が（たとえば）著者名順に並んでいるところへ， 新しく到着した本のカードを追加するときは， まさにこの二段目を行なうことになるだろう。 すなわち，すでに並んでいるカードを新しいカードがはいるべきところで二組に分け， そこに新しいカードを挿入することになる。
(6.1.3) 図書カードのときは， 新しく挿入したカードよりも「大」なるカードはカード一枚の厚みの分だけ奥にずれる。 しかし，コンピュータではそう簡単にはいかないので，次のような操作を行なう。
(6.1.4) つまり，二段目の各ステップ（＝ a[i] を挿入するステップ）は
とする。 ただし，逆転していなかったらそこで打ち切る。 そこが挿入すべき位置だから。
(6.1.5) 上の例ではこうなる。
| 03 | 05 | 48 | 92 | 13 | -- | -- |
| ↓ | ||||||
| 03 | 05 | 48 | 13 | 92 | -- | -- |
| ↓ | ||||||
| 03 | 05 | 13 | 48 | 92 | -- | -- |
次に 05 と 13 とを比較するが， ここは逆転していないので，これで操作は終わりである。 その先の比較はする必要がない。
(6.1.6) 極めて重要なヒント： for ループを使い，継続条件を 「j > 1 かつ a[j-1] が a[j] より大きい限り」 とする。「かつ」はＣ言語では && と書くのだった。
(6.1.7) そして，これを，i が 2 から N まで， i の値を一つずつ大きくしながら行なってゆく。
(6.1.8) 初めからソートされていた場合が最も lucky な場合であり， 比較回数は N-1, 交換回数は 0 である。 逆順にソートされていた場合が最悪の場合であり， a[i] を挿入する際の比較回数・交換回数はどちらも i-1 となって，全体ではどちらもおよそ N2/2 となる。 平均的な場合には， a[i] を挿入するときの比較・交換回数（の期待値） はどちらもおよそ i/2 であろう。 よって，全体では， 比較・交換回数ともに最悪の場合の半分， すなわち N2/4 とみてよいだろう。 どちらもΟ(N2) である。 以下に述べる二つのアルゴリズムとは異なり， もしも配列がほとんどソートされていれば比較回数も交換回数も小さいことに注意しよう。 Shell ソートでは，この事実を利用する。
(6.2.1) 前からの準備を元にして，以下のヒントを読みつつ， 乱数列で初期化された配列を挿入ソートでソートするプログラムを書け。 また，配列の大きさと比較回数・交換回数との関係を調べよ。 そして，メールでレポートせよ。 ファイル名は insert.c がよいかも知れない。 （英語では insertion sort と呼ばれるらしい。）
(6.2.2) 元にするのは，前回分で swap() と comp() を付け加えたソースファイルである。 これらの関数のテスト用として main() に書き加えた部分は削除しておく。
(6.2.3) まずは，配列の大きさを 8 から 10 程度とし， プログラムを完成する。 このときは swap() を呼ぶごとに print() を呼び，配列全体を画面に出力させる。 途中で「いまから a[5] (=17)を挿入します」） のようなメッセージを出すのは， 出力結果に区切りを入れて見やすくするためである。
#include ...
main() {
...
for (i = ?; i <= ?; i++) {
printf("いまから a[%d] を挿入します.\n", i); /* a[] の値も出力する？ */
for (j = ?; j ???; j??) {
...
swap(?, ?);
print();
}
}
}
(6.2.4)
#include ...
int ccount = 0; /* 比較（comp()）のカウンタ。0 で初期化 */
int scount = 0; /* 交換（swap()）のカウンタ。0 で初期化 */
main() {
int i, j;
printf("配列の大きさは %d です. ", N); /* 配列の大きさを出力 */
printf("…………田中美佐子\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];
}
関数 comp() が呼び出されるたびに変数 ccount の値が増されるので，
これで comp() が呼び出された回数がわかる。
変数 scount についても同様。
これで，比較回数・交換回数が (6.1.8) に書いた値に近いことを確認する。
(6.2.3) 違っていたら，前に戻ってやり直し。もしも， 正しくソートされるが理論上の回数の二倍近い回数になっている場合， 私を呼べ。 重大なヒントをさずけよう。
(6.2.4) ここまでできたら，print() の呼び出しを「/*」と 「*/」で囲んでコメントにし，配列の出力はいっさい行なわないようにする。 「いまから ... を挿入します.」の出力も同様にコメントとする。 なお，この授業で使っているコンパイラは実は C++ コンパイラなので， C++ でのコメントの記号，すなわち「//」を使ってもよい。 これを書くと，そこから行の終わりまでがコメントになる，という約束である。 配列の大きさ N をいくつに選ぶかは，下を参照。 このときの出力は次のようになる。
配列の大きさは .... です. …………田中美佐子 乱数の種は .......... です. ..... 回比較しました. ..... 回交換しました.
(6.2.5) メールは，必ず，この授業で配布したアカウントから送れ。 メールの本文冒頭に， 学籍番号，名列番号，氏名（として大学に届けてあるもの）を忘れずに書け。 次に，レポートの内容を，「挿入ソートのプログラムと実験結果」程度に， 簡潔に書け。
(6.2.6) その次に，プログラムを載せよ。 その際，Active! mail のメール作成画面の「添付ファイル」 *ではなく* 本文の中にソースファイルを貼りつけること。 プログラムは，下に指示するように， N の値を三通りに変えてコンパイル・実行するが， 載せるプログラムは N が指定のうちで最大のものとせよ。 また，実験を行なったプログラムそのものでなければならない。 （一部でも変更したときは，コンパイル・実行をやり直すこと。）
(6.2.7) 比較回数・交換回数を調べる際には， 配列の大きさ N の値を 100, 1000, 10000 の三通りに変えること。 それぞれの N について最低でも５回ずつくり返して実験せよ。 その際，乱数の種が毎回異なるようにするため， 一秒以内に二度以上プログラムを動かすな。
(6.2.8) 実験結果すべて（最低でも１５回分）を， 全部をまとめてコピペして送れ。 すなわち，プロンプトや「./a.out」， 「cc insert.c」を含んだままコピペせよ。 （編集すると間違うおそれがあるため。）
(6.2.9) 感想などの，上で書くよう指示したこと以外は書かなくてよい。 （書きたければ書いてもよい。）
(6.2.10) 宛て先は私（岩瀬）の実習用アカウント（(1.9.7) 参照）である。 件名は「kadai1」（←全て半角文字，アルファベットは小文字， 途中にスペースをいれない）とせよ。
(6.2.11) 出されたレポートは，なるべく早く採点し，必ず返事をメールで送る。 そこに「OK」と書かれていて初めて，その課題の点数を得たことになる。 「やり直し！」の場合，「OK」になるまで，訂正・加筆して，再提出せよ。 何回再提出しても，最後に「OK」になれば， 一度で「OK」になった人と同じ得点を与える。 なお，再提出の場合も，「あたかもそれが最初の提出であるかのように」書け。 （訂正箇所だけを送るのは不可。最初のメールを「転送」するのも不可。）
(6.3.1) 挿入ソートは N が 10000 でも一秒ほどで終わるので， 時間がはかりにくい。 N を 100000 にすると何十秒かかかるので， はかりやすくなる。
(6.3.2) 時間をコンピュータそのものに測定させるには， 「./a.out」の代わりに 「date; ./a.out; date」として動かす。 date は現在時刻を出力するコマンドだった。 次々をコマンドを実行させたい場合， セミコロンで区切る，という約束である。 開始直前と終了直後の時刻が表示されるので， 引き算をすればかかった時間がわかる。
(6.4.1) ここは，時間などに余裕がある人のためのオプション項目である。
(6.4.2) 配列 a[ ] を初期化する際，わざと偏ったやり方で行なったら， 比較回数や交換回数はどうなるだろうか？ 「a[i] = i;」と書けば元々データはソートされていたことになる。 「a[i] = N + 1 - i;」なら逆順。 「a[i] = i + rand() % 5;」とすれば 「だいたいそろっているが完全にはソートされていないデータ」になる。 （5 という数に特別な意味はない。）
(6.5.1) ここは，時間などに余裕がある人のためのオプション項目である。
(6.5.2) 本当にソートできたかどうかチェックするルーチンをつけてみよう。 配列 a[ ] に 0 が代入されていないこと，および， a[1] が a[2] 以下であること， a[2] が a[3] 以下であること， ………， a[N-1] が a[N] 以下であること， を順にチェックすればよい。 違っていたらメッセージを画面に出力させる。 独立した関数にしてもよいし， main() の最後に置いてもよいだろう。
(6.5.3) ※ 「a[i] = rand();」のほうで初期化する際， a[i] に 0 が代入されることがありえるから， 配列に 0 が代入されていたからといってプログラムが間違っているとはいえない。 しかし，N は RAND_MAX（§3.5.3 参照）よりずっと小さいので， 0 が代入される可能性はかなり低い。
(6.6.1) 「a[i] > a[i+1] を満たす i があったら a[i] と a[i+1] とを交換する。これをくり返してゆく」 というのがこのソートのアイディアである。 幼稚園の先生が園児を背の順に並ばせるとき， この方法を採用することもあるだろう。 そのような i のさがし方はいろいろ考えられる。 （そのうちのどれを採用するかをきちんと述べるまでは， これをアルゴリズムとは呼べない。）
(6.6.2) 次に示すのはその一つのやり方である。
これで，最大の値をもつもの（のうちの一つ）が a[N] にはいることを（頭の中で）確かめよ。 （幼稚園の先生が園児を背の順に並ばせる過程でいえば， どんな手順をとったことになるか？）
次に
これで，a[1] から a[N-1] までのうちで最大のもの （＝配列全体で言えば二番目に大きいもの）が a[N-1] にはいった。 以下はこれのくり返し。
(6.6.3) このアルゴリズムでの比較回数は (N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2, すなわち， およそ N2/2 である。 交換回数は最悪の場合（＝完全に逆順に並んでいた場合）が比較回数と同じ， 最も lucky な場合（＝元々ソートされていた場合）が 0 で， 平均するとおよそ N2/4 とみてよいだろう。 よって，全体では Ο(N2) のアルゴリズムである。
(6.6.4) 興味のある人はこのアルゴリズムでソートを行なうプログラムを書いてみよ。
(6.7.1) a[1] から a[i] までのうちで最大のものの添え字を求める操作を i-1 回の比較で行なう方法が存在する。 このことは容易だから認めよう。
(6.7.2)
これでソートが完了する。
(6.7.3) 全体の比較回数は (N-1) + (N-2) + ... + 1 = N(N-1)/2 回， 交換回数は N-1 回である。 （最大のものが最後にきていても，すなわち，交換の必要がなくても swap() を呼び出すほうが全体としては速い。 よって， 交換回数は「たかだか N-1 回」ではなくちょうど N-1 回である。）
(6.7.4) 以上から， このソートの比較回数は Ο(N2) であり， 交換回数は Ο(N) であることがわかる。 全体では Ο(N2) のアルゴリズムである。
(6.7.5) 興味のある人はこのアルゴリズムでソートを行なうプログラムを書いてみよ。
(6.7.6) ※ a[1] から a[i] までのうちで最大のものの添え字を求める際には， j < i なる j に対し a[1] から a[j] までで最大の値を持つものの添え字を保持しておくわけだが， より速いプログラムを書くなら，そこまでの最大値そのものも保持しておくほうがよい。 ただし，こうすると，前に書いた関数 comp() は使わないことになる。