(40.1) 互いに異なる三つの数 a, b, c を比較して小さい順に並べるとしよう。 下の図は、最初に a < b かどうかを調べ、「はい」なら上へ、 「いいえ」なら下へ進む、と読む。一番右に書かれているのが、得られた結論である。
+- 「a < b < c」
|
+- (b < c ?) -+
| | +- 「a < c < b」
| +- (a < c ?) -+
| +- 「c < a < b」
-(a < b ?) -+
| +- 「b < a < c」
| +- (a < c ?) -+
| | +- 「b < c < a」
+- (b < c ?) -+
|
+- 「c < b < a」
高々３回の比較で結論に至るが、これを２回に減らすことは不可能である。 それは、２回の分岐では４通りの結論しかありえないのに対し、 結論は 3! = 6 通りあるからである。
(40.2) 同様の議論により、 高々 k 回の比較で N 個の元をソートするプログラムがあったとすると、 2k ≧ N! が成り立つ。 自然対数をとると k log(2) ≧ log(N!) = log(1) + log(2) + log(3) + ... + log(N-1) + log(N) となる。 この右辺は、関数 y = log(x) の積分と比較することにより、 N log(N) - N + 1 よりも大きく、 (N+1) log(N+1) - N よりも小さいことがわかる。 N が十分大きければほぼ N log(N) とみなせる。 よって、 N が十分大きいとき、 “ほぼ k ≧ N log(N) / log(2)”である。 公式 logac = logab ・logbc, あるいは logac / logab = logbc を思い出すと、 これは“ほぼ k ≧ N log2(N)”となる。 情報科学では対数の底として 2 を選ぶことが多いらしい。 その約束を採用するなら、“ほぼ k ≧ N log(N)”と書ける。 オーダーで言えば、Ο(N log(N)) が限界となる。 これより真に小さいオーダーの計算量で済むアルゴリズムは存在しない。
(40.3) （ただし、これは、 二つの要素の比較と互換を基礎としてアルゴリズムを構成する限り、 の話である。 それ以外の、ソートに都合のよい機能を持ったコンピュータがでてきて、 基礎になる演算が比較・互換以外のものになれば、 その回数は上の限界よりも少ないことがあり得る。）
(40.4) 次から、Ο(N log(N)) のソートアルゴリズムを学ぶ。 オーダーの点から見れば、これよりも効率のよいアルゴリズムは存在しない。 あとは、係数をどれだけ小さくできるか、である。
(41.1) ヒープソートに登場する「ヒープ (heap)」は 「木」と呼ばれるデータ型の一種である。 一般の木を扱う方法はこの授業では取りあげない。 また、ヒープという言葉はコンピュータの世界ではこれ以外にもいろいろな意味で使われる。
(41.2) ここでは、 配列 a[1], ..., a[N] において、 「a[2*i] と a[2*i+1] は a[i] の子」 と考える。
(41.3) 次のような図を書いて考えるとわかりやすい。
a[1]
a[2] a[3]
a[4] a[5] a[6] a[7]
a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15]
N の値によっては、 この山から右下の一部が欠けたものになる。
(41.4) 上の例の“高さ”が 3 であるか 4 であるかは定義のしかたの問題だが、 いずれにせよ、ほぼ log(N) である。 （(40.2) に書いたように、対数の底は 2 である。）
(41.5) 「a[i] から a[j] までがヒープである」 とは、 a[i], a[i+1], ..., a[j] のうちで親子関係にある全てのペアについて、親が子以上であることをいう。
(41.6) 補題： a[i+1] から a[r] までがヒープになっているとき、 a[i] から a[r] までの要素の間で Ο(log(r)) 以下の回数の比較・交換を行ない、 a[i] から a[r] までをヒープにできる。
(41.7) 証明：次の例で考えよう。 a[4] から a[31] までがヒープになっている。 これを、a[3] から a[31] までがヒープになっているように変えたい。
35
82 37
97 67 96 95
96 95 49 37 76 92 94 58
57 21 81 19 06 22 23 26 72 18 26 32 46 57 02 18
いま考えている範囲より上の a[1] と a[2] は関係してこないし、 左半分もこれからの操作で変わらないので、「--」で置き換える。
--
-- 37
-- -- 96 95
-- -- -- -- 76 92 94 58
-- -- -- -- -- -- -- -- 72 18 26 32 46 57 02 18
ヒープの条件を満たしていないのは、 a[3] である 37 とその子との間のみである。 それ以外をいったん「--」に置き換えてみる。
--
-- 37
-- -- 96 95
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
ここで、「この三つの元のうちの二つに互換をほどこし、 この三つの元の間では親が子以上となるようにせよ」と言われたら、 三つの元のうちで一番大きい 96 を親の 37 と入れ替えることになる。
--
-- 96
-- -- 37 95
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
こうなった。「--」で置き換えてあった部分を戻そう。
--
-- 96
-- -- 37 95
-- -- -- -- 76 92 94 58
-- -- -- -- -- -- -- -- 72 18 26 32 46 57 02 18
こんどは、一段下にさがった 37 とその子の間で大小関係が合わなくなった。 合わないのはそこだけである。
--
-- --
-- -- 37 --
-- -- -- -- 76 92 -- --
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
だから、この三つの間でまた同じことをする。 すなわち、一番大きい 92 を親の 37 と入れ替える。
--
-- --
-- -- 92 --
-- -- -- -- 76 37 -- --
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
「--」で置き換えてあった部分を戻すと次のようになる。
--
-- 96
-- -- 92 95
-- -- -- -- 76 37 94 58
-- -- -- -- -- -- -- -- 72 18 26 32 46 57 02 18
こんどは、37 とその子の間で大小関係があっている。 これで操作は完了である。 いま行なった比較や交換の回数は上の図の高さ、 すなわち log(r) の何倍かで押さえられる。
(41.8) ※ ここで、上にあがった 92 がその上の 96 と親子の関係になったが、 その間の大小関係は大丈夫だろうか、と気になるかもしれない。 が、 それはもともと親子関係にあったものが一段ずつ上にあがってまた親子になっただけなので大丈夫なのである。
(41.9) ※ 上で行なった操作を、別の言いかたで説明しよう。 a[3] だった 37 から下へ進む。 一般に子は二つあるが、より大きな子のほうへと進んでゆく。 すると、次のような曲がった道ができる。
--
-- 37
-- -- 96 --
-- -- -- -- -- 92 -- --
-- -- -- -- -- -- -- -- -- -- -- 32 -- -- -- --
仮定により、この列の中では数値は下へゆくほど小さくなり、上へゆくほど大きくなる。 ここに、挿入ソートと似た操作を行なうと、次のようになる。
--
-- 96
-- -- 92 --
-- -- -- -- -- 37 -- --
-- -- -- -- -- -- -- -- -- -- -- 32 -- -- -- --
これが上で行なった操作である。 位置が変わる要素はここで示した道の上にあるものだけであり、 しかもそれは一つ上にあがるだけである。 ここで少し考えると、 操作後は a[3] 以降がヒープになっていることがわかる。
(41.10) 上の操作を関数にしたものを void downheap(int i, int r) としよう。 ヒープソートの原理は次のとおりである。
第二段を説明する。 配列全体、すなわち a[1] から a[N] までがヒープになっていれば、 この中で最大の元は a[1] である。 だから、それを a[N] と交換すれば a[N] は確定する。 そして、a[2] から a[N-1] までは依然としてヒープである。 よって、次には a[N] はもう見ないことにして、 関数 downheap() を利用し a[1] から a[N-1] までをヒープに再構築する。 これのくり返しである。
(41.11) 第一段も第二段も、 一つの元を処理するのにかかる手間は Ο(log(N)) 以下であるから、 全体で Ο(N log(N)) 以下の計算量となる。 オーダーがこれより小さくはならないことは前のセクションで見たので、 ヒープソートの計算量は Ο(N log(N)) である。 これは Ο(N2) だったいままでのソートよりもすぐれたアルゴリズムである。
(42.1) 課題１と同様のことを、ヒープソートについて行なえ。
(42.2) まず、GNOME 端末の「編集」「現在のプロファイル...」「スクロール」をクリック。 そして、「スクロールバックのサイズ」を 1000 行に増やしておこう。 こうしておけば、配列の大きさ N を 31 にして実験しても大丈夫である。
(42.3) 挿入ソートのプログラムをコピーしたものから始めよう。 ファイル名は heap.c でよいだろう。 関数 print() を次で置き換える。 これは、N の値が 16 以上 31 以下のとき、 配列に代入されている値を上の (41.7) のようなスタイルで出力するものである。 （スペースの数を調整してあるので、コピー & ペーストすることを強くすすめる。）
void print(void) {
int i;
printf(" %02d\n", a[1]);
printf(" %02d %02d\n", a[2], a[3]);
for (i = 4; i <= 7; i++) {
printf(" %02d ", a[i]);
}
printf("\n");
for (i = 8; i <= 15; i++) {
printf(" %02d ", a[i]);
}
printf("\n");
for (i = 16; i <= N; i++) {
printf("%02d ", a[i]);
}
printf("\n");
}
(42.4) 関数 downheap() では、 まず、a[i] とその左右の子（もしあれば）とを比較する。 親が最大だったらそれでおしまい。 子のほうが大きかったら、左右のうちで大きいほうと親とを入れ換え、 次は注目箇所をその子に移動する。 すなわち、i を変更する。 これのくり返しである。 よって、全体は次のような感じになるだろう。
（この関数の中での関数 comp() の呼び出しは四回で済む。 すぐに思いつかない人は、 五回以上になってもよいから正しく動くものを書いてみて、 あとで減らすことを考えよう。）
void downheap(int i, int r) {
for (ここは空白; ... <= r; ここも空白) { /* この範囲内に子がある限り */
if (左右に子がいる) {
if (親が最大) {
return; /* このときはヒープ化完了 */
} else if (左の子が最大) {
swap(i, 2*i); /* 親と左の子を交換 */
i = 2*i; /* 注目箇所を左の子に移動 */
} else { /* 右の子が最大のとき */
...
...
}
} else { /* 左の子のみのとき */
if (親が大きい) {
return; /* このときはヒープ化完了 */
} else { /* 左の子が大きいとき */
...
}
}
}
}
(42.5) 今回は、main() は比較的容易である。 まずは、main() は (41.10) の第一段のみとし、 関数 downheap() が正しく書けたかどうかのチェックを行なう。 途中経過のメッセージも出すとよい。 「a[3] から最後までをヒープにします」 「ヒープ化完了」など。
(42.6) 第一段は downheap(i, N) を実行するが、このとき、 第二の引数は N で、一定である。 N が偶数の場合と奇数の場合の両方で、downheap() が正しく書けているかどうかチェックする必要がある。 第一段で左の子しかいない場合が発生するための条件は N が偶数であることだから。
(42.7) 第一段が正しく書けたと確信できたら、第二段を追加する。 （今回は、for ループが二つ並ぶことになる。 二重ループではない。）
(42.8) 第二段の途中メッセージは 「a[9] は確定しました. a[1] から a[8] までをヒープに再構築します」 などがよいだろう。
(42.9) 件名は「kadai3」（←全て半角文字、アルファベットは小文字、 途中にスペースをいれない）とせよ。 これ以外の注意点は課題１と同じである。
(42.10) N の値を大きくしての実験は、 N を 10000, 100000, 1000000 にして、五回ずつ行なえ。
(42.11) N の値を大きくして実験をするようになったら、 関数 print() は使えなくなってしまうが、 レポートにはそのまま残しておくこと。
前に §35 に書いたような偏った初期化をした場合のヒープソートの比較・交換回数を調べよ。
前に (39.6) で述べた実験を、ヒープソートについても行なえ。