単連結リストの整列 #94 試行回数を増やして計測する

#92の処理時間計測プログラムでは基数ソートの計測をするにはデータサイズが小さいようである。

...snip
int main(void)
{
    const int nelems[] = {500, 707, 1000, 1414, 2000, 2828, 4000};
    const int ntrials[] = {200, 140, 100, 70, 50, 35, 25};
...snip

200から1600の範囲で計測していたリストの要素数を500から4000の範囲に変更し、
試行回数も要素数との積が38400になるようにしていたものを、約100000になるように増加した。

以下はUbuntu上で実行している。
単連結リストをバケツソートによる基数ソートで処理した結果は、

# nelems elapsed
500 45.0
707 64.3
1000 90.0
1414 128.6
2000 180.0
2828 257.1
4000 360.0

双方向連結リストを基数ソートで処理した結果は、

# nelems elapsed
500 50.0
707 71.4
1000 90.0
1414 142.9
2000 180.0
2828 314.3
4000 400.0

単連結リストか双方向連結リストかによらずほぼ同じ処理時間であり、
また時間計算量は要素数の一次オーダになっていることが分かる。

比較のために、隣接交換法および基本選択法によって双方向連結リストを整列した時の結果も示す。
隣接交換法の場合、

# nelems elapsed
500 270.0
707 528.6
1000 1030.0
1414 2114.3
2000 4240.0
2828 9057.1
4000 18600.0

基本選択法の場合、

# nelems elapsed
500 170.0
707 335.7
1000 680.0
1414 1314.3
2000 2720.0
2828 5685.7
4000 11720.0

隣接交換法よりも基本選択法の方が処理時間が短いが、
要素数が増加してくると線形に長くなる基数ソートに比べて、
もっと高い次数で増加していくのは隣接交換法も基本選択法も同様である。