本当も何も元から難しいクイックソート

id:sumii先生出題 本当はむずかしいクイックソート

なんか大学でやったようなやってないような課題.
等価性の問題に乗り遅れた?今読んでる本[珠玉のプログラミング]に関連する内容なので考えてみた.

参照先のページをコピペするとcygwin上でsegmentation faultるので,配列はヒープ上に持たせた.
timeコマンドの精度は…DLL参考記録ということで.

ランダムな配列(はえ

	srand(0);
	for (i = 0; i < N; i++) {
		a[i] = rand() % 100000000;
	}
	> gcc -O3 qsort-rand-100000000.c -o qsort-rand-100000000
	> ./qsort-rand-100000000.exe
	real    0m0.500s
	user    0m0.358s
	sys     0m0.000s

降順な配列(おせぇ

	for (i = 0; i < N; i++) {
		a[i] = -i;
	}
	> gcc -O3 -o qsort-worst qsort-worst.c
	> time ./qsort-worst
	real    9m45.033s
	user    0m0.015s
	sys     0m0.031s

問題0 昇順な配列

予想

まぁまぁ速く終わる.
一回の関数呼び出し中でごちゃごちゃ入れ替わるけど,右端か左端で別れて一つずつ要素が決まるような気がした.
脳内再帰は3ネストくらいが限界だった….

結果
	for (i = 0; i < N; i++) {
		a[i] = i;
	}
	real    0m3.336s
	user    0m3.124s
	sys     0m0.031s
理由

大まかには予想通りの動きだが,左端から位置が決定していく.
左端のピボットには小さい数が割り当てられるので,swapが多く実行され,
ランダムな入力の動作時より遅くなる.

問題1 ランダムだが要素が被りすぎな配列

予想

やや遅い.
等しい要素は全てswapするのでそれなりに時間が掛かる(worstよりは速い)

結果
	srand(0);
	for (i = 0; i < N; i++) {
		a[i] = rand() % 100;
	}
	real    0m25.035s
	user    0m23.655s
	sys     0m0.046s
理由

これは予想通り :)
要素が等しい場合はその都度swapを行ってしまうので遅くなる.
全く同じ要素のみから構成された配列でも,配列のサイズと同じ回数くらいswapする.
また要素を一つ減らした同じ配列についてまたswapが繰り返されるので,
全く同じ要素からなるサイズNの配列についてのswapの回数はN+(N-1)+(N-2)+...+1となり,(部分的には)O((N^2)/2)時間掛かってしまう.
ただし,今回は乱数で選んだのでNが大きくなりすぎる(==極端に遅くなる)ことは起きづらいと思う.

まとめ

イメージとは違ってなかったのでよし.*1

*1:レポートとしては….