(39.1) 配列の要素 a[i] と a[j] を比較するには if (a[i] > a[j]) のように書けばよいわけだが、 あとの都合で
int comp(int i, int j) {
return a[i] - a[j];
}
という関数にしておこう。こう定義したうえで
if (comp(i, j) > 0) と書けば同じことである。
(39.2) main() の最後に
if (comp(1, 2) > 0) {
swap(1, 2);
}
print();
と書き足して実験してみよう。
どうなれば実験成功かは各自で考えること。
(40.1) しばらくの間、プログラミングを離れて、 ソートの「アルゴリズム」について考えてみよう。 「アルゴリズム」とは、 問題を解くための手順をあいまいさのないように書いたもののことである。
(40.2) ※ 配列の要素には等しい値をもつものがあるかも知れないが、 その場合のことには深入りしないので、各自考えること。 また、添字の範囲のうち、常識でわかるものは断らないことにする。
(40.3) まずは、素朴なソートを考える。 「素朴なソート」というのは特定のアルゴリズムを指すのではなく、 「プログラミングの経験を少し積んだ人がちょっと考えれば思いつくようなソートのアルゴリズム」 を呼ぶ一般的な名前である。 これらは、すぐあとで学ぶアルゴリズムに比べて効率が悪いので時間をかけて論じても意味がない。 そこで、個々の「素朴なソート」にははっきりと決まった名前がないことが多いようである。
(40.4) ソートのアルゴリズムの良し悪しは、 比較回数（＝配列の要素を比較する回数）、 交換回数（＝配列の要素の互換を行なう回数） をデータの大きさ N の関数とみなして判定する。 少ない回数で済むほうがよいアルゴリズムである。
(40.5) オーダーを表すオミクロン記法を復習しよう。 ここでは N→∞ のときだけを考える。 N の関数 f(N) と g(N) があって、 「N→∞ のとき |f(N)/g(N)| は有界」なら、 f(N) = Ο(g(N)) と書き、 「f(N) のオーダーは g(N) のオーダー以下である」などと言う。 たとえば N(N-1)/2 = Ο(N2) である。 N2/4 = Ο(N2) でもあるが、 N(N-1)/2 = Ο(N2) = N2/4 から N(N-1)/2 = N2/4, などと考えてはいけない。
(40.6) アルゴリズムの良し悪しを論ずる際には、 必要な手数をデータの大きさ N の関数とみなしたときのオーダーがまず第一に問題となる。 オーダーが同じ場合は係数が次の問題となる。 すなわち、同じ Ο(N2) であった場合には、 N2/4 のほうが N2/2 よりも優れたアルゴリズムとなる。
(40.7) Ο(N log(N)) のアルゴリズムは Ο(N2) のアルゴリズムでもあるわけだが、 わざわざ悪く言うこともないのでそれを 「Ο(N2) のアルゴリズム」と呼ぶことは滅多にない。
(40.8) 比較回数と交換回数とでオーダーが違うこともあるが、 その場合は オーダーの大きいほうが全体のオーダーを決めることになる。 たとえば、 Ο(N2) である関数 N2/2 と Ο(N) である関数 N とを足した N2/2 + N が Ο(N2) ではあるが Ο(N) ではないように。
(41.1) 「a[i] > a[i+1] を満たす i があったら a[i] と a[i+1] とを交換する。これをくり返してゆく」 というのがこのソートのアイディアである。 幼稚園の先生が園児を背の順に並ばせるとき、 この方法を採用することもあるだろう。 そのような i のさがし方はいろいろ考えられる。 （そのうちのどれを採用するかを述べるまでは、 これをアルゴリズムとは呼べない。）
(41.2) 次に示すのはその一つのやり方である。
(41.3) このアルゴリズムでの比較回数は (N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2, すなわち、 およそ N2/2 である。 交換回数は最悪の場合（＝完全に逆順に並んでいた場合）が比較回数と同じ、 最も lucky な場合（＝元々ソートされていた場合）が 0 で、 平均するとおよそ N2/4 とみてよいだろう。 よって、全体では Ο(N2) のアルゴリズムである。
(41.4) 興味のある人はこのアルゴリズムでソートを行なうプログラムを書いてみるとよい。 （課題にはしない。）
(42.1) a[1] から a[i] までのうちで最大のものの添え字を求める操作を i-1 回の比較で行なう方法が存在する。 このことは容易だから認めよう。
(42.2)
(42.3) 全体の比較回数は (N-1) + (N-2) + ... + 1 = N(N-1)/2 回、 交換回数は N-1 回である。 （最大のものが最後にきていても、すなわち、交換の必要がなくても swap() を呼び出してしまうことにすれば、 交換回数は「たかだか N-1 回」ではなくちょうど N-1 回である。）
(42.4) 以上から、 このソートの比較回数は Ο(N2) であり、 交換回数は Ο(N) である。 全体では Ο(N2) のアルゴリズムである。
(42.5) 興味のある人はこのアルゴリズムでソートを行なうプログラムを書いてみるとよい。 （課題にはしない。）
(43.1) 挿入ソートは、次に学ぶ Shell ソートの基礎になる。 次の二つを利用して配列をソートするものである。
| 48 | -- | -- | -- | -- | -- | -- |
| 03 | 05 | 48 | 92 | 13 | -- | -- |
| ↓ | ||||||
| 03 | 05 | 13 | 48 | 92 | -- | -- |
(43.2) これを挿入ソートと呼ぶ理由は、 図書カード --- 数学教室図書室にもあるような、図書室で蔵書を検索する際に使うカード --- が（たとえば）著者名順に並んでいるところへ、 新しく到着した図書のカードを追加するときのことを想像してみてほしい。 まさにこの二段目を行なうことになるだろう。 すなわち、すでに並んでいるカードを新しいカードがはいるべきところで二組に分け、 そこに新しいカードを挿入することになる。
(43.3) 図書カードのときは、 新しく挿入したカードよりも「大」なるカードはカード一枚の厚みの分だけ奥にずれる。 しかし、コンピュータではそう簡単にはいかないので、次のような操作を行なう。
(43.4) つまり、二段目の各ステップは
(43.5) 上の例ではこうなる。
| 03 | 05 | 48 | 92 | 13 | -- | -- |
| ↓ | ||||||
| 03 | 05 | 48 | 13 | 92 | -- | -- |
| ↓ | ||||||
| 03 | 05 | 13 | 48 | 92 | -- | -- |
(43.6) プログラムでは、 「j > 1 かつ a[j-1] > a[j] である限り」 と考え、for ループを使うとよいだろう。 「かつ」はＣ言語では && と書くのだった。
(43.7) そして、これを、i が 2 から N まで、 i の値を一つずつ大きくしながら行なってゆく。
(43.8) 初めからソートされていた場合が最も lucky な場合であり、 そのときの比較回数は N-1, 交換回数は 0 である。 逆順にソートされていた場合が最悪の場合であり、 このときはどちらもおよそ N2/2 となる。 平均的な場合には、 a[i] を挿入するときの比較・交換回数はどちらも i/2 であろう。 よって、全体では比較・交換回数とも N2/4 とみてよいだろう。 どちらもΟ(N2) である。 前の二つのアルゴリズムと異なり、 もしも配列がほとんどソートされていれば比較回数も交換回数も小さいことに注意。
(44.1) 乱数列で初期化された配列を、挿入ソートでソートするプログラムを書け。 また、配列の大きさと比較回数・交換回数との関係を調べよ。 そして、メールでレポートせよ。
#include ...
int ccount = 0; /* 比較（comp()）のカウンタ。0 で初期化 */
int scount = 0; /* 交換（swap()）のカウンタ。0 で初期化 */
main() {
...
printf("配列の大きさは %d です.\n", N); /* 配列の大きさを出力 */
/* ここでソートを行なう */
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];
}
(44.2) プログラムも送ること。 その際、Active! mail のメール作成画面の「添付ファイル」 *ではなく* 本文の中にソースファイルを貼りつけること。 また、プログラムは、そのままでコンパイルできるものを送ること。 たとえば、 「#define N /* ここに配列の大きさを入れてコンパイルしてください */」 と書いて送られるとこのままではコンパイルできず、 採点に時間がかかるからやめるように、という意味である。
(44.3) 上の 4 番については、配列の大きさ N の値を最低でも３通りに変えること。 N の値があまり小さいと意味がないし、 大きすぎると実行に時間がかかりすぎる。 それぞれの N について最低でも５回ずつくり返して実験せよ。 その際、乱数の種が毎回異なるようにするため、 一秒以内に二度以上プログラムを動かすな。 出力結果をメールに貼りつけたうえで、回数の平均値を計算せよ。 それから、理論上の値などと比較せよ。 感想は書かなくてもよい。
(44.4) 宛て先は私（岩瀬）の実習用アカウント（間違って二つできてしまった (35.9) のうちのあとのほう参照）です。 件名は「kadai3」（←全て半角文字、アルファベットは小文字、 途中にスペースをいれない）としてください。 自分の学籍番号、氏名（として大学に届けてあるもの） をメールの *本文内にも* 書くのを忘れずに。 締め切りは、諸君の進みぐあいを見たうえで決め、 この実習の最初のページに発表します。
(45.1) ここは、時間などに余裕がある人のためのオプション項目である。
(45.2) 配列 a[ ] を初期化する際、わざと偏ったやり方で行なったら、 比較回数や交換回数はどうなるだろうか？ 「a[i] = i;」と書けば元々データはソートされていたことになる。 「a[i] = N + 1 - i;」なら逆順。 「a[i] = i + rand() % 5;」とすれば 「だいたいそろっているが完全にソートされていないデータ」になる。 （5 という数に特別な意味はない。）
(46.1) ここは、時間などに余裕がある人のためのオプション項目である。
(46.2) 本当にソートできたかどうかチェックするルーチンをつけてみよう。 配列 a[ ] に 0 が代入されていないこと、および、 a[1] が a[2] 以下であること、 a[2] が a[3] 以下であること、 ………、 a[N-1] が a[N] 以下であること、 を順にチェックすればよい。 違っていたらメッセージを画面に出力させる。
(46.3) 独立した関数にしてもよいし、 main() の最後に置いてもよいだろう。