(32.1) ソートプログラムの多くは、 互換、 すなわち配列の二つの要素の交換からできている。 そこで、まず、互換を行なう関数を書こう。
(32.2) §31 で完成させたプログラムに、 関数 void swap(int i, int j) を書き加えよ。 この関数は、 要素 a[i] と a[j] の値を入れかえるものとする。 i と j が範囲内にあるかどうかはチェックしなくてよろしい。 プロトタイプ宣言もつけ加えること。
(32.3)
a[i] = a[j];
a[j] = a[i];
ではだめである。
最初は i と j とは等しくないと仮定して書いてみて、
書けたものが i と j が等しいときも正しく動くかどうか考えよ。
(32.4) もちろん、 この関数を呼び出してみなければ、正しく書けたかどうかはわからない。 それには、main() の最後に
swap(3, 8);
print();
のように付け加えればよいだろう。
これで a[3] と a[8] が入れかわっていれば OK である。
ほかに swap(8, 3) や swap(3, 3) も試すこと。
(32.5) ※ swap(-1, 8) や swap(3, N+1) を実行させるプログラムは、 配列の添字が範囲外になるので誤ったプログラムである。 そのことを理解したうえで、そういうプログラムを書いて実行してみよ。 おそらく、ここのコンピュータでは、エラーメッセージなどは出ないであろう。 前者では a[8] に、後者では a[3] に、 配列の“外”にあった値がはいってくることになるが、 それは 0 であることが多い。確かめよ。
(32.6) ※ これから書くプログラムは、少しずつ複雑になってゆく。 その際、間違って swap(-1, 8) や swap(3, N+1) を実行するようなプログラムを書いてしまうことはよくある。 配列を初期化する際、値の範囲を 1 から 99 までとしておいたのは、 print() が 0 を出力したら間違いだとすぐにわかるためであった。 a[0] に 0 を代入しておいたのも同様の理由からである。
(33.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) と書けば同じことである。
プロトタイプ宣言も付け足しておくこと。
(33.2) main() の最後に
if (comp(1, 2) > 0) {
swap(1, 2);
}
print();
と書き足して実験してみよう。
どうなれば実験成功かは各自で考えること。
(34.1) ソートプログラムは必ず二重以上のループになる。 二重ループの書き方について、やさしい例で練習しよう。
(34.2) 次のプログラムは、掛け算九九の表を印字するものである。 これを見て、二重ループのしくみを学べ。 いままでに習った知識で理解できるはずである。
#include <stdio.h>
main() {
int i, j;
for (i = 1; i <= 9; i++) {
for (j = 1; j <= 9; j++) {
printf("%d*%d=%2d ", i, j, i*j);
}
printf("\n");
}
}
(34.3) 次に、表
1*1= 1 1*2= 2 1*3= 3 1*4= 4 1*5= 5 1*6= 6 1*7= 7 1*8= 8 1*9= 9 2*2= 4 2*3= 6 2*4= 8 2*5=10 2*6=12 2*7=14 2*8=16 2*9=18 3*3= 9 3*4=12 3*5=15 3*6=18 3*7=21 3*8=24 3*9=27 4*4=16 4*5=20 4*6=24 4*7=28 4*8=32 4*9=36 5*5=25 5*6=30 5*7=35 5*8=40 5*9=45 6*6=36 6*7=42 6*8=48 6*9=54 7*7=49 7*8=56 7*9=63 8*8=64 8*9=72 9*9=81を出力するプログラムを書くとしよう。 これも掛け算九九の表だが、3*2 は 2*3 と同じだからという理由で省略し、 n の段は n*n 以降のみを書いたものである。 （昔はそう習ったらしい。 すなわち、昔は「8*3=24（はっさんにじゅうし）」などは習わなかったらしい。）
(34.4) これを書くときは、まず
for (i = 1; i <= 9; i++) {
/* ここで i の段を出力する */
}
と考える。
そして、コメントを置いた部分に i の段を出力するループを書けばよいが、
そのときには i は定数と思って書く。
よって、たとえば
for (j = i; j <= 9; j++) {
...
}
printf("\n");
のようになるだろう。
(34.5) 数学で和の記号 ∑ が二重になった場合の考え方と似ている。
(35.1) しばらくの間、プログラミングを離れて、 ソートの「アルゴリズム」について考えてみよう。 「アルゴリズム」とは、 問題を解くための手順をあいまいさのないように書いたもののことである。
(35.2) ※ 配列の要素には等しい値をもつものがあるかも知れないが、 その場合のことには深入りしないので、各自考えること。 また、添字の範囲のうち、常識でわかるものは断らないことにする。
(35.3) まずは、素朴なソートを考える。 「素朴なソート」というのは特定のアルゴリズムを指すのではなく、 「プログラミングの経験を少し積んだ人がちょっと考えれば思いつくようなソートのアルゴリズム」 を呼ぶ一般的な名前である。
(36.1) ソートのアルゴリズムの良し悪しは、 比較回数（＝配列の要素を比較する回数）、 交換回数（＝配列の要素の互換を行なう回数） をデータの大きさ N の関数とみなして判定する。 少ない回数で済むほうがよいアルゴリズムである。
(36.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) である。 N2/4 = Ο(N2) でもあるが、 N(N-1)/2 = Ο(N2) = N2/4 から N(N-1)/2 = N2/4, などと考えてはいけない。
(36.3) アルゴリズムの良し悪しを論ずる際には、 必要な回数をデータの大きさ N の関数とみなしたときのオーダーがまず第一に問題となる。 オーダーが同じ場合は係数が次の問題となる。 すなわち、同じ Ο(N2) であった場合には、 N2/4 のほうが N2/2 よりも優れたアルゴリズムとなる。
(36.4) Ο(N log(N)) のアルゴリズムは Ο(N2) のアルゴリズムでもあるわけだが、 わざわざ悪く言うこともないのでそれを 「Ο(N2) のアルゴリズム」と呼ぶことは滅多にない。
(36.5) 比較回数と交換回数とでオーダーが違うこともあるが、 その場合は オーダーの大きいほうが全体のオーダーを決めることになる。 たとえば、 Ο(N2) である関数 N2/2 と Ο(N) である関数 N とを足した N2/2 + N が Ο(N2) ではあるが Ο(N) ではないように。
(37.1) 「a[i] > a[i+1] を満たす i があったら a[i] と a[i+1] とを交換する。これをくり返してゆく」 というのがこのソートのアイディアである。 幼稚園の先生が園児を背の順に並ばせるとき、 この方法を採用することもあるだろう。 そのような i のさがし方はいろいろ考えられる。 （そのうちのどれを採用するかを述べるまでは、 これをアルゴリズムとは呼べない。）
(37.2) 次に示すのはその一つのやり方である。
(37.3) このアルゴリズムでの比較回数は (N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2, すなわち、 およそ N2/2 である。 交換回数は最悪の場合（＝完全に逆順に並んでいた場合）が比較回数と同じ、 最も lucky な場合（＝元々ソートされていた場合）が 0 で、 平均するとおよそ N2/4 とみてよいだろう。 よって、全体では Ο(N2) のアルゴリズムである。
(37.4) 興味のある人はこのアルゴリズムでソートを行なうプログラムを書いてみよ。
(38.1) a[1] から a[i] までのうちで最大のものの添え字を求める操作を i-1 回の比較で行なう方法が存在する。 このことは容易だから認めよう。
(38.2)
(38.3) 全体の比較回数は (N-1) + (N-2) + ... + 1 = N(N-1)/2 回、 交換回数は N-1 回である。 （最大のものが最後にきていても、すなわち、交換の必要がなくても swap() を呼び出してしまうことにすれば、 交換回数は「たかだか N-1 回」ではなくちょうど N-1 回である。）
(38.4) 以上から、 このソートの比較回数は Ο(N2) であり、 交換回数は Ο(N) である。 全体では Ο(N2) のアルゴリズムである。
(38.5) 興味のある人はこのアルゴリズムでソートを行なうプログラムを書いてみよ。
(38.6) ※ a[1] から a[i] までのうちで最大のものの添え字を求める際には、 j < i なる j に対し a[1] から a[j] までで最大の値を持つものの添え字を保持しておくわけだが、 より速いプログラムを書くなら、そこまでの最大値そのものも保持しておくほうがよい。 ただし、こうすると、前に書いた関数 comp() は使わないことになる。