最速のクイックソート(Fortran)

クイックソートが速いのは分かっていますが、コーディングの仕方によって速度は変わります。
本稿では、ネット上で公開されているどのクイックソートが早いのか調べていきます。

最も早いクイックソートはNUMPACのプログラムでした。

比較プログラム


比較するプログラムはネット上で公開されているクイックソート+αです。
対象は、倍精度実数をソートするプログラム、です。

1. 再帰を用いたクイックソート(f90)

t-nissieの日記: 【電脳】Fortranで書いたクイックソート

2. 再帰を用いないクイックソート(f90)

[Fortran]再帰を使わないquicksortその2 -fortran66の日記

※ただし、私が割と変えていますので、オリジナルそのものではないということを注記しておきます。この変更によって、実行速度はほぼほぼ変わらないことは確認しています。

3. Netlibのクイックソートdsort.f

https://www.netlib.org/slatec/src/dsort.f

4. NUMPACのクイックソート(sortdk.f)

SORTPACK(SORTxK,SORTxy,SRTVxz) (スカラー又はベクトルデータの内部ソーティング)

5. ヒープソート

fortran90によるヒープソートとバブルソート -シキノート

以上の5つのプログラムを比較していきます。
メインプログラムはこちら↓

コンパイルは

gfortran -O3 (ソートのプログラム達) main.f90

で行いました。

結果


結果を示します。
横軸にデータ数、縦軸にソートに掛かった時間を示しました。
”ソートに掛かった時間”とは、同じデータ数でソートを100回繰り返した時の1回当たりの時間です。


それぞれ、
赤線:再帰有りクイックソート
青線:再帰無しクイックソート
緑線:Netlibのクイックソート
紫線:NUMPACのクイックソート
黒線:ヒープソート
です。
最も早いのがNUMPAC, 最も遅いのがヒープソートだと分かりました。

ヒープソートもクイックソートも大体\(O(n\log n)\)ですので、グラフの傾きは両者でほとんど変わりません。再帰有りの方が遅い、という結果は面白いです。
先入観で”再帰は遅い”と考えていたのですが、そんなことはありませんでした。

続いて、同じデータを対数で見てみると以下の通りです。

走査したデータサイズの範囲では変化は有りません。更に大規模になれば、違いが見えてくるかもしれません。