(9.1.1) a[left], a[left+1], a[left+2], ..., a[right] から一つの元を選び、その値を pivot とする。 このとき、Ο(right-left+1) の計算量でこれらを並びかえて、 次を満たすようにする。 （right-left+1 はここに現れる項の個数である。）
(9.1.2) どの元を pivot に選んでもよいが、 ここでは左端の元 a[left] を選ぶことにする。 （以下ではそれを p とも書く。）
+-+---------------------------------------------------------------------------+ |p| | +-+---------------------------------------------------------------------------+ ^ ^ left right
これを、配列のこの部分の大きさ right-left+1 に比例する計算量で下のように並べかえる。 （具体的なやりかたは後述。）
+--------------------------------+-+------------------------------------------+
| |p| |
+--------------------------------+-+------------------------------------------+
ここは pivot 未満の元のみ ここは pivot 以上の元のみ
（下組） （上組）
(9.1.3) 次のステップでは、下組・上組にそれぞれ同じことをくり返す。 これがクイックソートの原理である。 くり返すところに、§7 で学んだ再帰を用いることになる。 最初は left は 1, right は N でこの操作をおこなう。 やがて right-left+1 が 1 以下になるが、そのときは何もしなくてよい。
(9.1.4) 第一ステップの計算量は Ο(N) だった。 第二ステップの計算量を求めてみよう。 上組をさらに二つに分けるときの計算量は上組の長さに、 下組をさらに二つに分けるときの計算量は下組の長さに比例するから、 この二つの操作の計算量の和は最初のステップの計算量にほぼ等しい。 同様に考えて、この先のステップの計算量も、ほぼ同じである。
(9.1.5) pivot としてどんな値が選ばれるかによって、 上組と下組の長さは変わってくる。 毎回、上組と下組とがほぼ同数の元からなるように pivot の値がうまく選ばれれば、 必要なステップ数はほぼ log2(N) となる。 よって、全体の計算量は Ο(N log(N)) である。
(9.1.6) しかし、 毎回上組または下組が空になれば、くり返しの回数はほぼ N になり、 全体の計算量は Ο(N2) となる。 また、この場合、 N の値が大きいと再帰が深くなりすぎてプログラムが最後まで実行できないこともある。 これが、クイックソートの弱点である。
(9.1.7) 配列を乱数で初期化する限り、このようなことは滅多に起こらないから、 この授業では、この現象の避けかたまでは考えない。 しかし、どんなに確率が低くても、起こりえることには対処しなければ完全なプログラムとはいえない。 また、実際のデータでソートをおこなう場合、かえってこの現象が起きやすいこともある。 たとえば、すでにソートされているデータをもう一度ソートしようとした場合、 あるいは、 いったんソートしたデータの後ろにあとから到着した少数のデータを追加してソートする場合などがそれにあたる。
(9.1.8) （まったくの余談だが、諸君全員に書類を提出してもらうときなどに、 実際、これが起こる。提出された書類を名簿の順番に並べ終わってから、 「すみません、遅れました」と言って書類を持ってくる人がいることが多いのである！）
(9.1.9) 下組と上組に分ける方法を、具体的に説明する。 わかりやすさのため、「未満」を「小」、「以上」を「大」と書く。
37 26 07 48 17 32 29 78 p i j
i は pivot のすぐ右から始め、 j は範囲の一番右から始める。
i は pivot 未満の元をスキップして右に進み（＝増加し）、 j は pivot 以上の元をスキップして左に進む（＝減少する）。
37 26 07 48 17 32 29 78
p 小 小 大 小 大
i j
スキップが終わったとき、上のようであれば、 a[i] と a[j] を交換する。 次のようになる。
37 26 07 29 17 32 48 78
p 小 小 小 大 大
i j
次は、i を 1 だけ増やし、j を 1 だけ減らしてから、 同様に、pivot との比較をおこなう。
37 26 07 29 17 32 48 78
p 小 小 小 大 大
i j
次のように、i と j とがすれ違う。
37 26 07 29 17 32 48 78
p 小 小 小 小 小 大 大
j i
こんどは、a[i] と a[j] とを交換してはいけない。 そして、交換の操作はこれで終わりである。
(9.1.10) 次は別の例である。
43 38 25 53 ?? 17 92 68 p 小 小 大 小 大 大 i j
53 と 17 を交換する。
43 38 25 17 ?? 53 92 68
p 小 小 小 大 大 大
i j
次は i と j が等しくなるが、 この場合も上と同じことをおこなう。 ?? が「小」の場合、「大」の場合について、それぞれどうなるか考えよ。
(9.1.11) そのあと、pivot をこの範囲内のどれかと交換する。 どれとか？ 考えよ。
(9.2.1) 課題２と同様のことを、クイックソートについておこなえ。
(9.2.2) 挿入ソートのソースファイルをコピーしたものから始めよう。 ファイル名は quick.c でよいだろう。 挿入ソートの for の二重ループは消す。 コメントにした関数 print() の呼び出しは復活させる。 a[left], ..., a[right] をソートする関数 void quicksort(int left, int right) を書き、 main() からは quicksort(1, N); と呼び出すことになる。 （プロトタイプ宣言を忘れないように。）
(9.2.3) 以下のプログラムの、 「?」となっている部分を正しく埋めれば完成する。
(9.2.4) 関数 quicksort() にミスがある状態で再帰呼び出しをしても意味がないので、 この関数を書いている間は最後の二行（quicksort() の再帰呼び出し） はコメントにしておく。（してある。）
void quicksort(int left, int right) {
int piv, i, j;
printf("quicksort(%d, %d) として呼び出されました.\n", left, right);
if (left ? right) { /* 考えている範囲が 1 個以下の元からなる場合 */
return;
}
piv = left;
i = left + 1; j = right;
for ( ; i ? j ; ) { /* i < j か？ i <= j か？ */
for ( ; i <= right && comp(i, piv) < 0; i++) {
;
}
for ( ; j >= left + 1 && comp(j, piv) >= 0; j--) {
;
}
if (i ? j) { /* i < j か？ i <= j か？ */
swap(i, j); i++, j--;
}
}
printf("pivot の a[%d](= %02d) を a[%d](= %02d) と交換.\n", piv, a[piv], ?, a[?]);
swap(piv, ?);
printf("つぎは quicksort(%d, %d), ", left, ?);
printf("quicksort(%d, %d) として呼び出します.\n", ?, right);
// quicksort(left, ?);
// quicksort(?, right);
}
(9.2.5) 関数 quicksort() を書いている間は、 N は 8 ぐらいで実験するのがよいだろう。
(9.2.6) N が 8 ぐらいで実験していると、 pivot がその範囲の最大値・最小値であるということはなかなか起こらないが、 そのような場合のチェックも必要である。 そのためには、N を 2 にしてのテストもおこなうとよい。 すると、次に quicksort(1, 0) や quicksort(3, 2) を呼び出す場合が出てくるが、 関数 quicksort() をよく見れば、 これらの呼び出しをしても実際には a[0] や a[3] にはアクセスしないことがわかるので、 問題はない。
(9.2.7) 件名は「?? kadai4」（←全て半角文字、 ?? は自分の id の下二けた、その後ろに半角スペース一つ、 kadai は小文字、 kadai と 4 の間にはスペースを入れない）とせよ。 これ以外の注意点は課題２と同じである。
(9.2.8) N の値を大きくしての実験は、 N を 10000, 100000, 1000000 にして、五回ずつおこなえ。
(9.2.9) 比較回数は N log2N を少し上回る程度、 交換回数はその四分の一程度になるはずである。 交換回数がなぜそうなるかは、各自で考えてみよ。 また、交換回数の二倍を N で割ると、 各要素が平均して何回うごいたかが求められる。 意外と少ないことがわかるだろう。
(9.3.1) 配列の大きさ N を 1000000 にし、 その初期化を a[i] = rand() % 99 + 1; とすると、 実行に時間がかかる。理由を考えよ。
(9.3.2) §6.6 に書いたような偏った初期化をすると、(9.1.6) に述べたような、 クイックソートにとって都合の悪い現象が起こりやすくなる。 実験してみよ。配列の大きさ N は 10000 でよい。
(9.3.3) 前に (7.2.6) で再帰の例としてあげた関数 int mymax() を参考にして、 クイックソートの再帰の最大の深さを調べよ。 それには、引数の d とは別に、 変数 ccount などと同じく、 main() の外で int depth = 0; として大域変数を宣言する。 それと d とをどう結びつけるかは各自で考えること。