(39.1) しばらくの間、プログラミングを離れて、 ソートの「アルゴリズム」について考えてみよう。 「アルゴリズム」とは、 問題を解くための手順をあいまいさのないように書いたもののことである。
(39.2) ※ 配列の要素には等しい値をもつものがあるかも知れないが、 その場合のことには深入りしないので、各自考えること。 また、添字の範囲のうち、常識でわかるものは断らないことにする。
(39.3) まずは、素朴なソートを考える。 「素朴なソート」というのは特定のアルゴリズムを指すのではなく、 「プログラミングの経験を少し積んだ人がちょっと考えれば思いつくようなソートのアルゴリズム」 を呼ぶ一般的な名前である。
(40.1) ソートのアルゴリズムの良し悪しは、 比較回数（＝配列の要素を比較する回数）、 交換回数（＝配列の要素の互換を行なう回数） をデータの大きさ N の関数とみなして判定する。 少ない回数で済むほうがよいアルゴリズムである。
(40.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, などと考えてはいけない。
(40.3) アルゴリズムの良し悪しを論ずる際には、 必要な回数をデータの大きさ N の関数とみなしたときのオーダーがまず第一に問題となる。 オーダーが同じ場合は係数が次の問題となる。 すなわち、同じ Ο(N2) であった場合には、 N2/4 のほうが N2/2 よりも優れたアルゴリズムとなる。
(40.4) Ο(N log(N)) のアルゴリズムは Ο(N2) のアルゴリズムでもあるわけだが、 わざわざ悪く言うこともないのでそれを 「Ο(N2) のアルゴリズム」と呼ぶことは滅多にない。
(40.5) 比較回数と交換回数とでオーダーが違うこともあるが、 その場合は オーダーの大きいほうが全体のオーダーを決めることになる。 たとえば、 Ο(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) ときどき、次のようなプログラムを書く人がいる。 これも正しく動く。
for (i = 1; i < N; i++) {
for (j = 1; j < N; j++) {
if (comp(j, j+1) > 0) {
swap(j, j+1);
}
}
}
バブルソートに似ているが、
比較回数が約 N2 回となるので、より劣るものである。
(44.1) ソートプログラムは必ず二重以上のループになる。 二重ループの書き方について、少しやさしい例で練習しよう。
(44.2) 表
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（はっさんにじゅうし）」などは習わなかったらしい。）
(44.3) これを書くときは、まず
for (i = 2; i <= 9; i++) {
/* ここで i の段を出力する */
}
と考える。
そして、コメントを置いた部分に i の段を出力するループを書けばよいが、
そのときには i は定数と思って書く。
よって、たとえば
for (j = i; j <= 9; j++) {
printf("%d*%d=%2d ", i, j, i*j);
}
printf("\n");
のようになるだろう。
(44.4) 数学で和の記号 ∑ が二重になった場合の考え方と似ている。