(53.1) a[left], ..., a[right] から一つの元を選び、 その値を pivot とする。 このとき、Ο(right-left+1) の計算量でこれらを並びかえて、
(53.2) もう少し説明しよう。 どの元を pivot に選んでもよいが、 ここでは左端の元 a[left] を選ぶことにする。 （以下ではそれを p とも書く。）
+-+---------------------------------------------------------------------------+ |p| | +-+---------------------------------------------------------------------------+これを、この部分の配列の大きさ right-left+1 に比例する計算量で下のように並べかえる。
+--------------------------------+-+------------------------------------------+
| |p| |
+--------------------------------+-+------------------------------------------+
ここは pivot 以下の元のみ ここは pivot 以上の元のみ
（下組） （上組）
(53.3) 次のステップでは、下組・上組にそれぞれ同じことをくり返す。 これがクイックソートの原理である。 （くり返すところに、前回学んだ再帰を用いることになる。 最初は left は 1, right は N でこの操作を行なう。 やがて right-left+1 が 1 以下になるが、そのときは何もしなくてよい。）
(53.4) 第一ステップの計算量は Ο(N) だった。 第二ステップの計算量を求めてみよう。 上組を二つに分けるときの計算量は上組の長さに、 下組を二つに分けるときの計算量は下組の長さに比例するから、 この二つの操作の計算量の和は最初のステップの計算量にほぼ等しい。 この先のステップの計算量も、ほぼ同じである。
(53.5) 毎回、上組と下組とがほぼ同数の元からなるように pivot の値がうまく選ばれれば、 必要なステップ数はほぼ log2(N) となる。 よって、全体の計算量は Ο(N log(N)) である。 ヒープソートも Ο(N log(N)) だったが、 クイックソートのほうが平均すると速いそうである。
(53.6) しかし、 毎回上組または下組が空になれば、くり返しの回数はほぼ N になり、 全体の計算量は Ο(N2) となる。 また、この場合、 N の値が大きいと再帰が深くなりすぎてプログラムが最後まで実行できないこともある。 これが、クイックソートの弱点である。
(53.7) 配列を乱数で初期化する限り、このようなことは滅多に起こらないから、 この授業では、この現象の避けかたまでは考えない。 しかし、どんなに確率が低くても、起こりえることには対処しなければ完全なプログラムとはいえない。 また、実際のデータでソートを行なう場合、かえってこの現象が起きやすいこともある。 たとえば、すでにソートされているデータをもう一度ソートしようとした場合、 あるいは、いったんソートしたデータの後ろにあとから到着した少数のデータを追加してソートする場合など。
(54.1) 課題４と同様のことを、クイックソートについて行なえ。
(54.2) a[left], ..., a[right] をソートする関数 void quicksort(int left, int right) を書き、 main() からは「quicksort(1, N);」と呼び出すことになる。
(54.3) 関数 quicksort() の書き方にはいろいろあるが、 そのうちの一つのアイディアを示す。 下の説明を参考にして、 「???」となっている部分を正しく埋めれば完成する。
void quicksort(int left, int right) {
int i, j;
printf("quicksort(%d, %d) として呼び出されました.\n", left, right);
if (left >= right) { /* 範囲が空か、一つの元からなるときは */
return; /* 何もしない */
}
printf("pivot は a[%d] = %d です.\n", left, a[left]);
j = left;
for (i = left + 1 ; i <= right; i++) {
if (comp(i, left) >= 0) {
???
} else {
???
}
printf("j = %d, i = %d です.\n", j, i); /* ★ */
}
printf("pivot の %d を正しい位置に入れます.\n", a[left]);
swap(left, j); /* pivot を a[j] と交換 */
print();
printf("次は a[%d] から a[%d] までと ", left, ???);
printf("a[%d] から a[%d] までとして呼び出します.\n", ???, right);
/*
quicksort(left, ???);
quicksort(???, right);
*/
}
for 文で
a[left + 1] から a[right] までのすべての元を
pivot と比較する。
もうひとつの変数 j は、
星印をつけた箇所を通るときおよび for ループを抜けた直後には
+-+---------+---------------+-------------------------------------------------+
|p| 未 満 | 以 上 | |
+-+---------+---------------+-------------------------------------------------+
^ ^
j i
それには、
+---- 交 換 ----+
| |
V V
+-+---------+---------------+-------------------------------------------------+
|p| 未 満 | : 以 上 | : |
+-+---------+---------------+-------------------------------------------------+
^ ^
j i
こうしておいて、最後に
a[left] (= pivot) とある元とを交換する。
(54.4) 関数 quicksort() にミスがある状態で再帰呼び出しをしてもほとんど意味がないので、 この関数を書いている間は最後の二行（quicksort() の再帰呼び出し） をコメントにしておくとよい。（そうしておいた。）
(54.5) quicksort() を書いている間は、 N は 8 ぐらいで実験するのがよいだろう。 再帰呼び出しをしなくても main() で比較回数・交換回数を出力させることは可能である。 そのときの比較回数は N-1 となるはずである。 交換回数も、比較的容易にわかるある数と一致する。 その平均は約 N/2 になるはずである。
(54.6) N が 8 ぐらいで実験していると、 pivot がその範囲の最大値・最小値であるということはなかなか起こらないが、 その場合のチェックも必要である。 そのためには、N を 2, 3 などの小さな値にしてのチェックも行なうとよい。
(54.7) 件名は「kadai5」（←全て半角文字、アルファベットは小文字、 途中にスペースをいれない）としてください。 これ以外の注意点は課題４と同じです。
(54.8) ※ a[3] と a[3] とを交換するといった、 むだな操作が行なわれるかもしれないが、気にしなくてよい。 興味のある人は、 「それが起こるのはどんな場合か？」 「それを避けるようにプログラムを改良することに意味があるか？」 と考えてみよ。
(54.9) ※ クイックソートはソートの決定版だけあって、 非常に細かい改良まで研究されているようである。 ここに紹介したのは比較的わかりやすいバージョンの一つにすぎない。
(55.1) §41 に書いたような偏った初期化をすると、(53.6) に述べたような、 クイックソートにとって都合の悪い現象が起こりやすくなる。 実験してみよ。
(55.2) §51 で再帰の例としてあげた関数 int mymax() を参考にして、 クイックソートの再帰の最大の深さを調べよ。 ただし、引数の d とは別に、 変数 ccount などと同じく、 main() の外で int depth = 0; として大域変数を宣言する。 それと d とをどう結びつけるかは各自で考えること。
(55.3) 上で示したプログラムでは、 再帰呼び出しを行なわない状態での交換回数は平均すると約 N/2 だった。 これを N/4 まで減らすことができる。 それには、変数 i は左端から右へ、 j は右端から左へと動かし、 pivot よりも大きい a[i] と pivot よりも小さい a[j] とがみつかったら、 それらをある条件のもとで交換する。 これをくりかえせばよい。 下に概略を示す。興味のあるものは完成させてみよ。
i = left + 1; /* これより左は pivot 以下 */
j = right; /* これより右は pivot 以上 */
for ( ; i < j; ) {
for ( ; i <= right && comp(i, left) <= 0; i++) {
; /* pivot 以下のものをスキップ */
}
for ( ; j > left && comp(j, left) >= 0; j--) {
; /* pivot 以上のものをスキップ */
}
printf(" i = %d, j = %d です.\n", i, j);
if (???) {
swap(i, j); i++; j--;
print();
}
}
printf("いま i = %d, j = %d です.\n", i, j);
??? /* ここで、場合分けをして、a[left] としかるべき元とを交換する */
print();