クイックソートに限らず、どのソートのプログラムでも、 main() の終わりでソートが正しく完了したかどうかをチェックすべきでした。 例えば次のように書いておくと、 配列が昇順になっていない場合、メッセージが出ます。 （メッセージの中の「#######」は目立たせるためのもので、 それ以外の意味はありません。 また、ここでエラーメッセージが出なくても、 正しくソートされているとは限りません。）
for (i = 0; i < N-1; i++) {
if (a[i] > a[i+1]) {
printf("####### error! #######\n");
}
}
ただし、これでは逆転している箇所の数だけメッセージが出てしまいます。
チェック用ルーチンなのでそれでもいいと思いますが、
次のようにすればメッセージは一度しか出なくなります。
for (i = 0; i < N-1 && a[i] <= a[i+1]; i++) {
;
}
if (i != N-1) {
printf("####### error! #######\n");
}
ループを抜けたあとで変数 i の値をチェックし、
ソートにミスがあってループを抜けたのかそうでないのかを判定しています。
さらに、次のようにすることで、この部分をより速くできます。ただし、配列は int a[N+1]; と、要素を一つ多くとってあるとします。 （ソートするのは従来通り a[0] から a[N-1] までです。）
a[N] = -1; /* 番兵 */
for (i = 0; a[i] <= a[i+1]; i++) {
;
}
if (i != N-1) {
printf("####### error! #######\n");
}
a[N] には -1 を入れておき、
for ループでは添字の範囲を気にせずに、
値が逆転しているところを探します。
a[0] ... a[N-1] はすべて 0 以上だったので、
ソートが成功している場合でも
i が N-1 になれば継続条件が偽となってループを抜けます。
よって、無限ループにはいったり、
添字がとんでもないところを指したりすることはありません。
この a[N] が「番兵」です。 （このテクニックのことも番兵と呼ぶことがあります。）
上の第二のプログラムではループを回るごとに二つの不等式をチェックしました。 ここではそれが一つになっています。 その分だけ高速化がはかれるというわけです。 （ただし、ここではほとんど意味がありません。 ソートそのものが Ο(N logN) なのに対し、 チェックルーチンは Ο(N) だからです。 実際にも、ここは一瞬で終わります。）
われわれはソートプログラムの速さを考える際、 配列の要素どうしの比較・交換回数だけを問題にしました。 しかし、より速いプログラムをめざすには、 このような点までも考える必要があります。
関数 quicksort() は説明したとおりに働きさえすれば、 中でどんなアルゴリズムを使っていても自由なのですが、 うまへたがあります。 再帰呼び出しの部分をコメントにして実行し、 比較・交換の回数を表示させると、うまへたがわかります。
right - left + 1 を N とおきましょう。 比較回数は N-1 回が最良です。 pivot 以外の元は一度は pivot と比較しなければならないからです。 そして、ここまで減らすことが可能です。
交換回数は、次のように考えます。 簡単のため、pivot と同じ値の元はないとしましょう。 pivot より小さい元が a 個、 pivot より大きい元が b 個あったとします。 ソート後はこうなります。
+-------+-+---------+ | |p| | +-------+-+---------+ <- a -> <-- b -->ソート前に左側にあった「より大きい元の数」と、 ソート前に右側にあった「より小さい元の数」は等しいはずです。 これらの元は左右で入れ換えなければなりませんから、 これらの数が交換回数の最小です。
さらに、配列は十分に性能のよい乱数で初期化されていると仮定し、 pivot / RAND_MAX を p とおくと、 pivot より小さい元は pN 個、 pivot より大きい元は (1-p)N 個あると思ってよいでしょう。 ソート前に左側にあった「より大きい」元の数は p(1-p)N 個、 右側にあった「より小さい」元の数も p(1-p)N 個と思えます。 よって、p(1-p)N が交換回数の最小です。 それをプログラムに出力させるなら、 例えば次のようになります。
double p;
p = (double) pivot / RAND_MAX;
printf("理論的な交換回数の最小は約 %.0f.\n", p * (1-p) * N);