ソートアルゴリズムの比較

ソートアルゴリズムを各種準備し（昇順、降順含む）、その計算時間を比較した例です。

単純に値の大小を比較し並べ替えるシンプルなソート、C言語でクイックソートを実装したもの、qsort 関数によりクイックソートを行うもの、の 3 種類準備しています。
100,200,400,800,1600,3200,6400,12800,25600,51200,102400 個（計11回の処理時間比較）の値を並べ替えた際の計算時間結果は以下のグラフになっています（Y軸はログスケール）。

（黒：シンプルソート、赤：クイックソート、青：qsort 関数）

グラフを見てみると、それぞれ指数関数的に計算時間が増えていることが分かりますが、それぞれの傾きが異なり、qsort よりも自前のクイックソートを用いた処理時間が短いことが分かります。
（コンパイルオプションには -ffast-math -O4 を指定）

CPUや処理系にも依存する部分ですが、102400 個程度の配列では 1 秒にも満たない時間なので、どちらでも良さそうですが、非常に大きな配列を扱う場合には参考になるかと思います。


実行結果