(52.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 通りあるからである。
(52.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 log(N)) よりも効率のよいアルゴリズムは存在しないことがわかる。
(52.3) 情報科学では対数の底として 2 を選ぶことが多いらしい。 そうすれば、上で求めた限界は約 N log(N) と書ける。
(53.1) ヒープソートに登場する「ヒープ (heap)」は 「木」と呼ばれるデータ型の一種である。 一般の木を扱う方法はこの授業では取りあげない。 また、ヒープという言葉はコンピュータの世界ではこれ以外にもいろいろな意味で使われる。
(53.2) ここでは、 配列 a[1], ..., a[N] において、 「a[2*i] と a[2*i+1] は a[i] の子」 と考える。
(53.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 の値によっては、
この山から右下の一部が欠けたものになる。
(53.4) 上の例の“高さ”を 3 とするか 4 とするかは定義の決め方の問題だが、 いずれにせよ、ほぼ log(N) である。
(53.5) 「a[i] から a[j] までがヒープである」 とは、 a[i], a[i+1], ..., a[j] のうちで親子関係にある任意のペアに対し、親が子以上であることをいう。
(53.6) 補題： a[i+1] から a[r] までがヒープになっているとき、 この範囲の要素の間で Ο(log(r)) 以下の回数の比較・交換を行ない、 a[i] から a[r] までをヒープにできる。
(53.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
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
さらに、これからの操作で変わらない部分も置き換える。
--
-- 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) の何倍かで押さえられる。
(53.8) ※ ここで、上にあがった 92 がその上の 96 と親子の関係になったが、 その間の大小関係は大丈夫だろうか、と気になるかもしれない。 が、 それはもともと親子関係にあったものが一段ずつ上にあがってまた親子になっただけなので大丈夫なのである。
(53.9) ※ 上で行なった操作を、別の言いかたで説明しよう。 a[3] だった 37 から下へ進む。 一般に子は二つあるが、より大きな子のほうへと進んでゆく。 すると、次のような曲がった道ができる。
--
-- 37
-- -- 96 --
-- -- -- -- -- 92 -- --
-- -- -- -- -- -- -- -- -- -- -- 32 -- -- -- --
仮定により、この列の中では数値は下へゆくほど小さくなり、上へゆくほど大きくなる。
ここに、挿入ソートと似た操作を行なうと、
--
-- 96
-- -- 92 --
-- -- -- -- -- 37 -- --
-- -- -- -- -- -- -- -- -- -- -- 32 -- -- -- --
となる。これが上で行なった操作である。
位置を変える要素はここで示した道の上にあるものだけであり、
しかもそれは一つ上にあがるだけである。
ここで少し考えると、
操作後は a[3] 以降がヒープになっていることがわかる。
(53.10) 上の操作を関数にしたものを void downheap(int i, int r) としよう。 ヒープソートの原理は次のとおりである。
(53.11) 第一段も第二段も、 一つの元を処理するのにかかる手間は Ο(log(N)) 以下であるから、 全体で Ο(N log(N)) 以下の計算量となる。 オーダーがこれより小さくはならないことは前のセクションで見たので、 ヒープソートの計算量は Ο(N log(N)) である。 これは Ο(N2) だったいままでのソートよりもすぐれたアルゴリズムである。
(54.1) 課題４と同様のことを、ヒープソートについて行なえ。
(54.2) まず、GNOME 端末の「編集」「現在のプロファイル...」「スクロール」をクリック。 そして、「スクロールバックのサイズ」を 1000 行に増やしておこう。 こうしておけば、配列の大きさ N を 31 にして実験しても大丈夫である。
(54.3) Shell ソートのプログラムをコピーしたものから始めよう。 関数 print() を次で置き換える。
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");
}
これは、N の値が 16 以上 31 以下のとき、
配列に代入されている値を上の (53.7) のようなスタイルで出力するものである。
(54.4) 関数 downheap() では、 まず、a[i] とその左右の子（もしあれば）とを比較する。 親が最大だったらそれでおしまい。 子のほうが大きかったら、左右のうちで大きいほうと親とを入れ換え、 次は注目箇所をその子に移動する。 すなわち、i を変更する。 これのくり返しである。 よって、全体は次のような感じになるだろう。
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 { /* 左の子が大きいとき */
...
}
}
}
}
(54.5) 今回は、main() は比較的容易である。 まずは、main() は (53.10) の第一段のみとし、 関数 downheap() が正しく書けたかどうかのチェックを行なう。 正しく書けたと確信できたら、 main() に (53.10) の第二段を追加する。
(54.6) 途中経過のメッセージも出すとよい。 「a[3] から a[31] までをヒープにします」、 「a[9] は確定しました」など。
(54.7) 件名は「kadai5」（←全て半角文字、アルファベットは小文字、 途中にスペースをいれない）としてください。 これ以外の注意点は課題４と同じです。
(54.8) N の値を大きくして実験をするようになったら、 関数 print() は使えなくなってしまうが、 レポートにはそのまま残しておくこと。