単連結リストの整列 #83 基本選択法の性能評価

例によって整列に要する時間を計測する#71のプログラムに基本選択法の整列コードをリンクして実行する。
単連結リストintlistを利用した場合、

# nelems ncmps nswps elapsed
200 19900.0 194.2 36.5
300 44850.0 293.8 78.1
400 79800.0 393.5 135.4
600 179700.0 592.9 296.9
800 319600.0 792.6 520.8
1200 719400.0 1193.1 1187.5
1600 1279200.0 1591.4 2083.3

比較回数は途中打ち切り無しの隣接交換法と同じ回数が常に必要だが、
交換回数は明らかに要素数の一次オーダでおさえられており、
隣接交換法からは交換回数が劇的に少なくなっている。
所要時間についても隣接交換法よりもずいぶん短く処理できるようになっている。

双方向連結リストintdlistを利用すると、

# nelems ncmps nswps elapsed
200 19900.0 194.2 26.0
300 44850.0 293.8 62.5
400 79800.0 393.5 104.2
600 179700.0 592.9 218.8
800 319600.0 792.6 437.5
1200 719400.0 1193.1 968.8
1600 1279200.0 1591.4 1708.3

使用データが同じなので比較と交換の回数は当然同じになる。
所要時間は単連結リストよりもさらに少しだけ短くて済んでいる。