(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) 件名は「??? kadai3」（←全て半角文字、 ??? は自分の履修者番号、その後ろに半角スペース一つ、 kadai は小文字、 kadai と 3 の間にはスペースを入れない）とせよ。 これ以外の注意点は課題１と同じである。
(9.2.8) N の値を大きくしての実験は、 N を 10000, 100000, 1000000 にして、五回ずつおこなえ。
(9.2.9) 比較回数は N log2N を少し上回る程度、 交換回数はその四分の一程度になるはずである。 交換回数がなぜそうなるかは、各自で考えてみよ。 また、交換回数の二倍を N で割ると、 各要素が平均して何回うごいたかが求められる。 意外と少ないことがわかるだろう。
(9.3.1) main() では quicksort(1, N) をおこないその次に比較回数・交換回数の出力をおこなうが、 その直後にこれらをもう一度繰り返すとどうなるか？ 配列の大きさ N は 10000 でよい。
(9.3.2) 配列の大きさ N を 1000000 にし、 その初期化を a[i] = rand() % 99 + 1; とすると、 実行に時間がかかる。理由を考えよ。
(9.3.3) §6.11 に書いたような偏った初期化をすると、(9.1.6) に述べたような、 クイックソートにとって都合の悪い現象が起こりやすくなる。 実験してみよ。配列の大きさ N は 10000 でよい。
(9.3.4) 前に (7.2.6) で再帰の例としてあげた関数 int mymax() を参考にして、 クイックソートの再帰の最大の深さを調べよ。 それには、引数の d とは別に、 変数 ccount などと同じく、 main() の外で int depth = 0; として大域変数を宣言する。 それと d とをどう結びつけるかは各自で考えること。
この授業で取り上げない C 言語の重要な事項として、ポインタがある。 ポインタには変数のアドレスを格納できる。 まずは、変数のアドレスに関連するプログラムを示す。
#include <stdio.h>
int main() {
int x;
printf("%p\n", &x);
}
手元のパソコンでは出力は 000000000061FE1C となった。 これは、変数 x に割り当てられたメモリのアドレスである。 （このコンパイラは十六進表記を採用している。）
変数名 x の前に & をつけて &x とすると、 x に格納されている値ではなく、 x に割り当てられたメモリのアドレスを意味するようになる。 アドレスを出力させる場合には %p と書く。
関数 scanf() で入力を受けつける場合は変数名の前に & をつけた。 つまり、「これこれ番地のメモリに値を入れてください」と scanf() に命令しているのである。
学術メディア創成センター演習室のパソコンでは、 Windows のほかに Linux も使える。 Linux は UNIX とほぼ同じように使える OS である。 Linux にはいろいろな種類があるようだが、 はいっているのはそのうちの Ubuntu である。
OS 選択画面で Linux を選ぶ。
ユーザー名は KAINS ID から @kains.net を取り除いたもの。 パスワードは Windows のときと同じである。
左端の一番上が「Firefox ウェブ・ブラウザ」。 アカンサスポータルにアクセスできることを確認した。
その二つ下に「ファイル」がある。 これが Windows の Explorer に相当する。
左端の一番下、正方形が 3 × 3 に並んでいるのが、 「アプリケーションを表示する」である。ゲームもいくつかはいっている。
「ファイル」の中の、何もないところを右クリックし 「端末で開く」とすると、「端末」と呼ばれる、 Windows のコマンド・プロンプトに相当するものが開く。 コンパイルは Windows と全く同じように、「gcc hello.c」とする。 実行ファイルを動かすのは「./a.out」である。 「ファイル」の中で新規ファイルを作る方法は見つけられなかった。 代わりに、端末の中で「touch 新規ファイル名」とせよ。
「ファイル」の中でいままで作った .c ファイルを開くと、 （いわゆる）日本語は普通に表示される。 しかし、Windows と Linux ではデフォルトの（いわゆる）日本語コードが異なるため、 そのままコンパイル・実行すると文字化けする。 新規ファイルに全文をコピーする必要がある。
この端末では、 前回説明した画面制御エスケープシーケンスが有効である。
この端末の中で使えるコマンド cd, pwd, ls, cp, rm, mv などについては、 ネット検索して調べられたい。
Linux の終了は右上の「▼」である。