本当も何も元から難しいクイックソート
なんか大学でやったようなやってないような課題.
等価性の問題に乗り遅れた?今読んでる本[珠玉のプログラミング]に関連する内容なので考えてみた.
参照先のページをコピペすると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:レポートとしては….