(6.1.1) ソートの「アルゴリズム」について考えてみよう。 「アルゴリズム」とは、 問題を解くための手順をあいまいさのないように書いたもののことである。
(6.1.2) まずは、「素朴なソート」を考える。 これは特定のアルゴリズムの名前ではなく、 プログラミングの経験を少し積んだ人がちょっと考えれば思いつくものを呼ぶ、 一般的な名前である。
(6.2.1) ソートのアルゴリズムの良し悪しは、 比較回数（＝配列の中の二つの要素を比較する回数）、 交換回数（＝配列の中の二つの要素の互換をおこなう回数） を配列の大きさ N の関数とみなして判定する。 少ない回数で済むほうがよいアルゴリズムである。
(6.2.2) オーダーを表すオミクロン記法を復習しよう。 ここでは N→∞ のときだけを考える。 N の関数 f(N) と g(N) があって、 「N→∞ のとき |f(N)/g(N)| は有界」なら、 f(N) = Ο(g(N)) と書き、 「f(N) のオーダーは g(N) のオーダー以下である」などと言う。 たとえば N(N-1)/2 = Ο(N2) である。
(6.2.3) アルゴリズムの良し悪しを論ずる際には、 必要な回数を配列の大きさ N の関数とみなしたときのオーダーがまず第一に問題となる。 オーダーが同じ場合は係数が次の問題となる。 すなわち、同じ Ο(N2) であった場合には、 N2/4 のほうが N2/2 よりも優れたアルゴリズムとなる。
(6.2.4) Ο(N log(N)) のアルゴリズムは Ο(N2) のアルゴリズムでもあるわけだが、 わざわざ悪く言うこともないのでそれを 「Ο(N2) のアルゴリズム」と呼ぶことは滅多にない。
(6.2.5) 比較回数と交換回数とでオーダーが違うこともあるが、 その場合は オーダーの大きいほうが全体のオーダーを決める。 たとえば、 Ο(N2) である関数 N2/2 と Ο(N) である関数 N とを足した N2/2 + N が Ο(N2) ではあるが Ο(N) ではないように。
(6.3.1) 挿入ソートは、次の原理で配列をソートする。
| 48 | -- | -- | -- | -- | -- | -- |
| 03 | 05 | 48 | 92 | 13 | -- | -- |
| ↓ | ||||||
| 03 | 05 | 13 | 48 | 92 | -- | -- |
(6.3.2) 図書カード ―― 数学コース閲覧室にもあるような、図書室の蔵書を検索する際に使うカード ―― が（たとえば）著者名順に並んでいるところへ、 新しく到着した本のカードを追加するときは、 まさにこの二段目をおこなうだろう。 すなわち、すでに並んでいるカードを新しいカードがはいるべきところで二組に分け、 そこに新しいカードを挿入する。
(6.3.3) 図書カードのときは、 新しく挿入したカードよりも「大」なるカードはカード一枚の厚みの分だけ奥にずれる。 しかし、コンピュータではそう簡単にはいかないので、次のようにおこなう。
(6.3.4) つまり、二段目の各ステップ（＝ a[i] を挿入するステップ）は
とする。 ただし、逆転していなかったらそこで打ち切る。 そこが挿入すべき位置だから。
(6.3.5) 上の例ではこうなる。
| 03 | 05 | 48 | 92 | 13 | -- | -- |
| ↓ | ||||||
| 03 | 05 | 48 | 13 | 92 | -- | -- |
| ↓ | ||||||
| 03 | 05 | 13 | 48 | 92 | -- | -- |
次に 05 と 13 とを比較するが、 ここは逆転していないので、これで操作は終わりである。 その先の比較はする必要がない。
(6.3.6) 極めて重要なヒント： for ループを使い、継続条件を 「j > 1 かつ a[j-1] が a[j] より大きい限り」 とする。「かつ」は C 言語では && と書くのだった。 j の値は 1 ずつ減ってゆく。
(6.3.7) そして、これを、i が 2 から N まで、 i の値を 1 ずつ大きくしながらおこなってゆく。 だから、for ループは二重になる。
(6.3.8) 初めからソートされていた場合が最も lucky な場合であり、 比較回数は N-1, 交換回数は 0 である。 逆順にソートされていた場合が最も unlucky な場合であり、 a[i] を挿入する際の比較回数・交換回数はどちらも i-1 となって、全体ではどちらもおよそ N2/2 となる。 平均的な場合には、 a[i] を挿入するときの比較・交換回数（の期待値） はどちらもおよそ i/2 であろう。 よって、全体では、 比較・交換回数ともに最も unlucky な場合の半分、 すなわち N2/4 とみてよいだろう。 どちらもΟ(N2) である。 §6.8, §6.9 で述べる二つのアルゴリズムとは異なり、 もしも配列がほとんどソートされていれば比較回数も交換回数も小さいことに注意しておこう。
(6.4.1) 前からの準備を元にして、以下のヒントを読みつつ、 乱数列で初期化された配列を挿入ソートでソートするプログラムを書け。 そして、メールでレポートせよ。 ファイル名は自由だが、insert.c がよいかも知れない。 （英語では insertion sort と呼ばれるらしい。）
(6.4.2) 元にするのは、前回書いた、print() の本体を書き、 swap() と comp() を付け加えたソースファイルである。 これらの関数のテスト用として main() に書き加えた部分などは削除する。 すなわち、main() は次だけになる。
int main() {
printf("配列の大きさは %d です. ", N); /* 配列の大きさを出力 */
printf("…………岡田奈々\n"); /* 自分の氏名を出力 */
init(); /* 初期化 */
print(); /* 画面表示 */
}
(6.4.3) これの、最後の「print()」と「}」との間に、(6.3.7) で述べた二重ループがはいる。詳しく言うと、次のようにする。
初期化したのちは、配列 a[ ] に収められた値は、 関数 swap() によってのみ変更する。 すなわち、a[i] = a[i+1] などとは書かない。 プログラムを完成させるまでは、 関数 swap() で値が入れ替わるごとに配列の値すべてを表示させたいので、 swap() の中で print() を呼び出す。 このときは、配列の大きさは 8 でよい。 途中で「いまから a[5] (= 48) を挿入します.」） のようなメッセージを出すのは、 出力結果に区切りを入れて見やすくするためである。 （次を参照。）
#include ...
int main() {
int i, j;
...
print();
for (i = ?; i <= ?; i++) {
printf("いまから a[%d] (= %02d) を挿入します.\n", i, a[i]);
for (j = ?; j ? ? && ???; j??) {
swap(?, ?);
}
}
}
...
void swap(int i, int j) {
...
print(); /* 画面表示 */
}
(6.4.4) 正しくソートされることがわかったら、 次のように書き足して、比較回数、交換回数を調べる。
#include ...
int ccount = 0; /* 比較（comp()）のカウンタ。0 で初期化 */
int scount = 0; /* 交換（swap()）のカウンタ。0 で初期化 */
int main() {
int i, j;
printf("配列の大きさは %d です. ", N); /* 配列の大きさを出力 */
printf("…………岡田奈々\n"); /* 自分の氏名を出力 */
init();
print();
/* ここに、上で書いた二重ループによるソートの部分がくる */
printf("%d 回比較しました.\n", ccount); /* 比較回数を出力 */
printf("%d 回交換しました.\n", scount); /* 交換回数を出力 */
}
void swap(int i, int j) {
...
print(); /* 画面表示 */
scount++; /* ここを通るたびにカウンタが増える */
}
int comp(int i, int j) {
ccount++; /* ここを通るたびにカウンタが増える */
return a[i] - a[j];
}
関数 comp() が呼び出されるたびに変数 ccount の値が増されるので、 これで comp() が呼び出された回数がわかる。 変数 scount についても同様。
(6.4.5) 毎回「28 回比較しました」になる人は私を呼べ。 次に配列の大きさを 78 にして試す。 782/4 = 1521 である。 比較回数・交換回数が (6.3.8) に書かれた値に近ければよい。 もしも、 正しくソートされるが理論上の二倍近い比較回数になって直し方がわからない場合も私を呼べ。
(6.4.6) ここまでできたら、print() の *呼び出し* をコメントにし、 配列の出力はいっさいおこなわないようにする。 「いまから ... を挿入します.」の出力も同様にコメントとする。 なお、この授業で使っているコンパイラは実は C++ コンパイラなので、 C++ でのコメントの記号、すなわち「//」を使ってもよい。 これを書くと、そこから行の終わりまでがコメントになる、という約束である。 つまり、main() は
int main() {
...
printf("配列の大きさは %d です. ", N); /* 配列の大きさを出力 */
printf("…………岡田奈々\n"); /* 自分の氏名を出力 */
init(); /* 初期化 */
// print(); /* 画面表示 */
for (i = ?; i <= ?; i++) {
// printf("いまから a[%d] (= %02d) を挿入します.\n", i, a[i]);
for (j = ?; j ? ? && ???; j??) {
...
swap(?, ?);
}
}
...
}
のようになり、swap() は
void swap(int i, int j) {
...
// print(); /* 画面表示 */
scount++; /* ここを通るたびにカウンタが増える */
}
のようになる。
（関数 print() は一度も呼び出されないが、
そのまま残しておいてよい。）
このときの出力は次のようになる。 配列の大きさ N をいくつに選ぶかは、下を参照。
配列の大きさは .... です. …………岡田奈々 乱数の種は .......... です. ..... 回比較しました. ..... 回交換しました.
(6.4.7) メールは、必ず、この授業で配布したアカウントから送れ。 メールの本文冒頭に、 学籍番号、名列番号、氏名（として大学に届けてあるもの）を忘れずに書け。 次に、レポートの内容を、「挿入ソートのプログラムと実験結果」程度に、 簡潔に書け。
(6.4.8) その次に、プログラムを載せよ。 その際、KAINS Webmail のメール作成画面の「ファイルを添付」 *ではなく* 本文の中にソースファイルを貼りつけよ。 プログラムは、下に指示するように、 N の値を三通りに変えてコンパイル・実行するが、 載せるプログラムは N が指定のうちで最大のものとせよ。 また、実験をおこなったプログラムそのものでなければならない。
(6.4.9) 比較回数・交換回数を調べる際には、 配列の大きさ N の値を 100, 1000, 10000 の三通りに変えること。 それぞれの N について最低でも５回ずつくり返して実験せよ。 その際、乱数の種が毎回異なるようにするため、 一秒以内に二度以上プログラムを動かすな。 また、実験は、必ず、センターのパソコンでおこなえ。
(6.4.10) 実験結果すべて（最低でも 15 回分）を、まとめてコピペして送れ。 すなわち、プロンプトや「a」、 「gcc insert.c」を含んだままコピペせよ。 編集すると間違うおそれがあるからである。 なお、cmd からコピーする際には、範囲指定したのち、 Ctrl+C を押す。
(6.4.11) 感想などは書かなくてよい。書きたければ書いてもよい。
(6.4.12) 宛て先は私（岩瀬）の実習用アカウント（(1.8.8) 参照）である。 件名は「?? kadai2」（←全て半角文字、 ?? は自分の id の下二けた、その後ろに半角スペース一つ、 kadai は小文字、 kadai と 2 の間にはスペースを入れない）とせよ。
(6.4.13) 出されたレポートは、なるべく早く採点し、必ず返事をメールで送る。
そこに「OK」と書かれていて初めて、その課題の点数を得たことになる。 「やり直し！」の場合、「OK」になるまで、訂正・加筆して、再提出せよ。 何回再提出しても、最後に「OK」になれば、 一度で「OK」になった人と同じ得点を与える。 なお、再提出の場合も、「あたかもそれが最初の提出であるかのように」書け。 （訂正箇所だけを送るのは不可。最初のメールを「転送」するのも不可。）
(6.5.1) ここからあと（§6.6-6.9）は、 時間などに余裕がある人のためのオプション項目である。
(6.6.1) 配列 a[ ] を初期化する際、わざと偏ったやり方でおこなったら、 比較回数、交換回数はどうなるだろうか？ 「a[i] = i;」と書けば元々データはソートされていたことになる。 「a[i] = N + 1 - i;」なら逆順。 「a[i] = i + myrand() % 5;」とすれば 「だいたいそろっているが完全にはソートされていないデータ」になる。 （5 という数に特別な意味はない。）
(6.7.1) 本当にソートできたかどうかチェックするルーチンをつけてみよう。 配列 a[ ] に 0 が代入されていないこと、および、 a[1] が a[2] 以下であること、 a[2] が a[3] 以下であること、 ………、 a[N-1] が a[N] 以下であること、 を順にチェックすればよい。 違っていたらメッセージを画面に出力させる。 独立した関数にしてもよいし、 main() の最後に置いてもよいだろう。
(6.8.1) 「a[i] > a[i+1] を満たす i があったら a[i] と a[i+1] とを交換する。これをくり返してゆく」 というのがこのソートのアイディアである。 幼稚園の先生が園児を背の順に並ばせるとき、 この方法を採用することもあるだろう。 そのような i のさがし方はいろいろ考えられる。 （そのうちのどれを採用するかをきちんと述べるまでは、 これをアルゴリズムとは呼べない。）
(6.8.2) 次に示すのはその一つのやり方である。
これで、最大の値をもつもの（のうちの一つ）が a[N] にはいることを（頭の中で）確かめよ。 （幼稚園の先生が園児を背の順に並ばせる過程でいえば、 どんな手順をとったことになるか？）
次に
これで、a[1] から a[N-1] までのうちで最大のもの （＝配列全体で言えば二番目に大きいもの）が a[N-1] にはいった。 以下はこれのくり返し。
(6.8.3) このアルゴリズムでの比較回数は (N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2, すなわち、 およそ N2/2 である。 交換回数は最も unlucky な場合（＝完全に逆順に並んでいた場合）が比較回数と同じ、 最も lucky な場合（＝元々ソートされていた場合）が 0 で、 平均するとおよそ N2/4 とみてよいだろう。 よって、全体では Ο(N2) のアルゴリズムである。
(6.8.4) 興味のある人はこのアルゴリズムでソートをおこなうプログラムを書いてみよ。
(6.9.1) a[1] から a[i] までのうちで最大のもの （の一つ）の添え字を求める操作を i-1 回の比較でおこなう方法が存在する。 このやり方は比較的容易だから説明を省略する。
(6.9.2)
これでソートが完了する。
(6.9.3) 全体の比較回数は (N-1) + (N-2) + ... + 1 = N(N-1)/2 回、 交換回数は N-1 回である。 （最大のものが最後にきていても、すなわち、交換の必要がなくても swap() を呼び出すほうが全体としては速い。 よって、 交換回数は「たかだか N-1 回」ではなくちょうど N-1 回である。）
(6.9.4) 以上から、 このソートの比較回数は Ο(N2) であり、 交換回数は Ο(N) であることがわかる。 全体では Ο(N2) のアルゴリズムである。
(6.9.5) 興味のある人はこのアルゴリズムでソートをおこなうプログラムを書いてみよ。
(6.9.6) ※ a[1] から a[i] までのうちで最大のもの（の一つ）の添え字を求める際には、 j < i なる j に対し a[1] から a[j] までで最大の値を持つもの（の一つ）の添え字を保持しておくわけだが、 より速いプログラムを書くなら、そこまでの最大値そのものも保持しておくほうがよい。 ただし、こうすると、前に書いた関数 comp() は使わないことになる。
#include <stdio.h>
int main(){
int a, b;
scanf("%d %d", &a, &b);
printf("a = %d, b = %d.\n", a, b);
}
上のように書くと、「3 2」のように、 スペースで区切って二つの整数を一度に入力できる。 しかし、間違えて「3, 2」のようにカンマで区切ると、 まったく違う数値になってしまう。
#include <stdio.h>
int main(){
int a, b;
scanf("%d, %d", &a, &b);
printf("a = %d, b = %d.\n", a, b);
}
こんどは「3,2」のようにカンマで区切って入力する。 カンマを抜かすとまずいことになる。