(46.1) a[left], ..., a[right] から一つの元を選び、 その値を pivot とする。 このとき、Ο(right-left+1) の計算量でこれらを並びかえて、 次を満たすようにする。
(46.2) もう少し説明しよう。 どの元を pivot に選んでもよいが、 ここでは左端の元 a[left] を選ぶことにする。 （以下ではそれを p とも書く。）
+-+---------------------------------------------------------------------------+ |p| | +-+---------------------------------------------------------------------------+ ^ ^ left right
これを、配列のこの部分の大きさ right-left+1 に比例する計算量で下のように並べかえる。
+--------------------------------+-+------------------------------------------+
| |p| |
+--------------------------------+-+------------------------------------------+
ここは pivot 以下の元のみ ここは pivot 以上の元のみ
（下組） （上組）
(46.3) 次のステップでは、下組・上組にそれぞれ同じことをくり返す。 これがクイックソートの原理である。 くり返すところに、前回学んだ再帰を用いることになる。 最初は left は 1, right は N でこの操作を行なう。 やがて right-left+1 が 1 以下になるが、そのときは何もしなくてよい。
(46.4) 第一ステップの計算量は Ο(N) だった。 第二ステップの計算量を求めてみよう。 上組をさらに二つに分けるときの計算量は上組の長さに、 下組をさらに二つに分けるときの計算量は下組の長さに比例するから、 この二つの操作の計算量の和は最初のステップの計算量にほぼ等しい。 同様に考えて、この先のステップの計算量も、ほぼ同じである。
(46.5) pivot としてどんな値が選ばれるかによって、 上組と下組の長さは変わってくる。 毎回、上組と下組とがほぼ同数の元からなるように pivot の値がうまく選ばれれば、 必要なステップ数はほぼ log2(N) となる。 よって、全体の計算量は Ο(N log(N)) である。 ヒープソートも Ο(N log(N)) だったが、 クイックソートのほうが平均すると速いそうである。
(46.6) しかし、 毎回上組または下組が空になれば、くり返しの回数はほぼ N になり、 全体の計算量は Ο(N2) となる。 また、この場合、 N の値が大きいと再帰が深くなりすぎてプログラムが最後まで実行できないこともある。 これが、クイックソートの弱点である。
(46.7) 配列を乱数で初期化する限り、このようなことは滅多に起こらないから、 この授業では、この現象の避けかたまでは考えない。 しかし、どんなに確率が低くても、起こりえることには対処しなければ完全なプログラムとはいえない。 また、実際のデータでソートを行なう場合、かえってこの現象が起きやすいこともある。 たとえば、すでにソートされているデータをもう一度ソートしようとした場合、 あるいは、 いったんソートしたデータの後ろにあとから到着した少数のデータを追加してソートする場合などがそれにあたる。
(46.8) （まったくの余談だが、諸君全員に書類を提出してもらうときなどに、 実際、これが起こる。提出された書類を学籍番号順に整理し終わってから、 「すみません、遅れました」と言って書類を持ってくる人がいることが多いのである！）
(47.1) 課題１と同様のことを、クイックソートについて行なえ。
(47.2) 挿入ソートのソースファイルをコピーしたものから始めよう。 ファイル名は quick.c でよいだろう。 a[left], ..., a[right] をソートする関数 void quicksort(int left, int right) を書き、 main() からは quicksort(1, N); と呼び出すことになる。
(47.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) {
???
}
printf("j = %d, i = %d です.\n", j, i); /* ★ */
}
printf("pivot の %d を正しい位置に入れます.\n", a[left]);
swap(left, ?); /* pivot を a[?] と交換 */
print();
printf("次は a[%d] から a[%d] までと ", left, ???);
printf("a[%d] から a[%d] までとして呼び出します.\n", ???, right);
/*
quicksort(left, ???);
quicksort(???, right);
*/
}
変数 i と j とを用いているが、二重ループではない。 for 文で動かすのは i である。 a[left+1] から a[right] までのすべての元を pivot と比較する。 もうひとつの変数 j は、 for ループにはいる直前、 星印（「★」）をつけた箇所を通るとき、および for ループを抜けた直後には次を満たしているように、 for ループの本体（= 中カッコで囲まれた部分）で変化させる。
+-+---------+---------------+-------------------------------------------------+ |p| 未 満 | 以 上 | | +-+---------+---------------+-------------------------------------------------+ ^ ^ ^ left j i
それには、次のようにすればよい。
j の値をどう変化させるかは、各自で考えること。
+---- 交 換 ----+
| |
V V
+-+---------+-+-------------+-+-----------------------------------------------+
|p| 未 満 | : 以 上 | : |
+-+---------+-+-------------+-+-----------------------------------------------+
^ ^ ^
left j i
こうしておいて、最後に a[left] (= pivot) とある元とを交換する。 （どの元と交換するのかは、各自で考えること。）
(47.4) 関数 quicksort() にミスがある状態で再帰呼び出しをしてもほとんど意味がないので、 この関数を書いている間は最後の二行（quicksort() の再帰呼び出し） をコメントにしておくとよい。 （上ではそうしておいた。このように、複数行をまとめてコメントにすることもできる。）
(47.5) 関数 quicksort() を書いている間は、 N は 8 ぐらいで実験するのがよいだろう。 再帰呼び出しをしなくても main() で比較回数・交換回数を出力させることは可能である。 そのときの比較回数は N-1 となるはずである。 交換回数も、比較的容易にわかるある数と一致する。 その平均は約 N/2 になるはずである。
(47.6) N が 8 ぐらいで実験していると、 pivot がその範囲の最大値・最小値であるということはなかなか起こらないが、 そのような場合のチェックも必要である。 そのためには、N を 2 などの小さな値にしてのチェックも行なうとよい。
(47.7) 件名は「kadai4」（←全て半角文字、アルファベットは小文字、 途中にスペースをいれない）とせよ。 また、main() の中の次の部分を修正してほしい。
printf("配列の大きさは %d です.\n", N); /* 配列の大きさを出力 */
これを、次のように修正する。
printf("配列の大きさは %d です. ... 田中美佐子\n", N);
実際には自分の氏名を書くこと。
これは、
誰が書いたプログラムかを採点者が混同しないようにするための試みである。
これ以外の注意点は課題１と同じである。
(47.8) N の値を大きくしての実験は、 N を 10000, 100000, 1000000 にして、五回ずつ行なえ。
(47.9) ※ a[3] と a[3] とを交換するといった、 むだな操作が行なわれるかもしれないが、気にしなくてよい。 興味のある人は、 「それが起こるのはどんな場合か？」 「それを避けるようにプログラムを改良することに意味があるか？」 と考えてみよ。
(47.10) ※ クイックソートはソートの決定版だけあって、 非常に細かい改良まで研究されているようである。 ここに紹介したのは比較的わかりやすいバージョンの一つにすぎない。
(48.1) 配列の大きさ N を 1000000 にし、 その初期化を a[i] = rand() % 99 + 1; とすると、 実行に時間がかかる。理由を考えよ。
(48.2) §35 に書いたような偏った初期化をすると、(46.6) に述べたような、 クイックソートにとって都合の悪い現象が起こりやすくなる。 実験してみよ。
(48.3) 前に (39.6) で述べた実験を、クイックソートについても行なえ。
(48.4) §44 で再帰の例としてあげた関数 int mymax() を参考にして、 クイックソートの再帰の最大の深さを調べよ。 それには、引数の d とは別に、 変数 ccount などと同じく、 main() の外で int depth = 0; として大域変数を宣言する。 それと d とをどう結びつけるかは各自で考えること。
(48.5) 上で示した関数 quicksort() では、 再帰呼び出しを行なわない状態での交換回数は平均すると約 N/2 だった。 いま、再帰呼び出しを行なう直前までの操作（(46.2) で説明したもの）を 「並べ直し」と呼ぶことにし、その平均的な場合を考えてみよう。 pivot は並べ直しの後には中央に収まるだろう。 並べ直す前には、 左半分、右半分のそれぞれについて、 そのうち半分が pivot より大、半分が小、と考えられる。 左半分にあって大なるものと、右半分にあって小なるものとを交換すれば、 並べ直しができたことになる。 そのやり方での交換回数は約 N/4 である。
(48.6) 関数 quicksort() を改良し、 実際に交換回数を約 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();