質問: temp; } } void quick_sort(int* array, size_t length) { qsort(array, length, sizeof(int), numcmp); } int numcmp(const void* lhv, const void* rhv) { return *(int*)lhv - *(int*)rhv; } ``` ### 実行環境 OS:Ubuntu18.04 Cコンパイラ:gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0 ### 補足、実際に実行される方へ 実際に実行すると、bubble_sortのところで22秒ほど時間がかかってCPU使用率が100%になりました、ご注意下さい。 また、select_sortとquick_sortを細かく比較するときは、main()内の定数Array_lengthを大きくしてください。 その時にbubble_sortの処理時間が爆発的に大きくなりますので、main()内のsort_counter(bubble_sort, copy_array[0], Array_length, FUNC_NAME(bubble_sort));の箇所をコメントしていただく事をおすすめします。 分かりづらくてすみません。
回答: 解決済みのようですが、かなり間違いがあります。 ランダウの記号で示される計算量は最悪の場合を基準にしています。ですのでクイックソートのオーダはn*nが正解です、誤ってnlognと書かれた資料をどれだけ見たことか。つまり、配列内のデータ分布次第ではバブルソートにすら劣る可能性があります。いうまでもなく、本課題では乱数パターンに大きく依存します。 また、オーダはアルゴリズムと対象データサイズとの関係性を示すものであり、単位のない指標に過ぎません。異なるアルゴリズムのものの結果同士を直接比較しても期待通りとは限りません。例えばデータサイズを動かして処理時間の**増加具合を比較する**とかならわかりますが、異なるアルゴリズムの処理時間同士を直接比較するというのは統計処理として不適切です。 ちなみに、クイックソートはピボットの選び方で最悪の場合が変わります。qsort関数の実装は存じませんが、ピボットを端とするならば最悪の場合は整列済みの場合です。配列に一要素追加するたびにクイックソートするという実装を見たことがありますが、これはかなり酷い実装です。 さらに余談ですが、計算量といえば時間だけだなくメモリ量の尺度にもなるので、こちらの比較もしてみると面白いですよ。