授業の終わりのときに「まとめ」のようなことを話す時間をとらなかったので、 授業が終わってからだいぶ経ちますが、書いてみました。 その前に、クイックソートについてのコメントもあります。 （2005 年 10 月 05 日（水）記す）
クイックソートのプログラムを書いてみたがえらく遅い、 という相談が何件かありました。 プログラムを調べたところ、 配列を乱数で初期化するところが 「a[i] = rand() % 100;」のままの人が多かったようです。 「a[i] = rand();」とすると劇的に速くなります。 私のプログラムで実験したところ、以下に示すようになりました。
配列の大きさは 1000000 です. 比較 25694116 回 交換 4720284 回 再帰の最大の深さは 48 でした.
配列の大きさは 1000000 です. 比較 4268893525 回 交換 2190089 回 再帰の最大の深さは 13977 でした.
n 個からなる配列の要素がすべて同じ値の場合、 「pivot より小さいものが 0 個で pivot 以外の n-1 個はすべて pivot より大きい」 （あるいはその逆） と分けられるように関数 quicksort() を書いた人も多いでしょう。 そうすると、次の再帰呼び出しにあたっては、 これらを 0 個と n-1 個にわけて quicksort() を呼び出します。 以下同様に、このあと（およそ） n 回の再帰をくり返し、 各段階では配列の大きさに比例した回数の比較を行ないますから、 比較回数は Ο(n2) となってしまいます。
「a[i] = rand() % 100;」のままだと、同じ値をもつ要素が非常に多いので、 クイックソートが進んでソートする範囲に同じ数だけが並ぶようになると上で説明した状態に陥り、 それで遅くなるのでした。
こういう場合の対策も考えてクイックソートのプログラムを書くのは、 今回の授業より何段階か高いレベルの話です。
今回の授業では配列のソートのみを取り上げました。 最初の素朴なソートで配列の大きさが十万の場合、 私のプログラムでは 160 秒かかりました。 クイックソートで配列の大きさが百万の場合は 1 秒、 ヒープソートは 2 秒でした。 素朴なソートは Ο(N2) のアルゴリズムなので、 もしも素朴なソートで百万個の元をソートさせていたら、 およそ 160 * 10 * 10 = 16000 秒、すなわち 4 時間 26 分 40 秒もかかっていたでしょう。 普通、何も教わらないで自分で考えていたら、 素朴ソート（およびクイックソート）以外のアルゴリズムはなかなか思いつかないと思います。 自分より前に生きてきた人たちの得てきたものを学ぶ意義を、 こういったところで実感してもらえたらなあ、と思います。
ところで、 みなさんが専門にしている数学では、 有限個の実数のソートは一瞬で終わるとみなして議論を進めます。 「これらの固有値を小さい順に並べて λ1, λ2, ..., λn とします」 と書いたら、n がどんなに大きくても、一瞬で小さい順に並んだことになります。 人間には一瞬でできないことを一瞬でできたことにして話を先に進める数学って何なんだろう、 ということも、時間があったら考えてみてください。 この問題の答えは、私にもわかりません。