単連結リストの整列 #72 整列を途中で打ち切らない版の所要時間

整列処理の途中で対象のリストが整列済みになっても最後まで整列処理を続けるバージョンのlistsortをリンクして、
前回と同じ測定プログラムを実行してみる。

# nelems ncmps nswps elapsed
200 19900.0 9878.0 307.3
300 44850.0 22434.0 929.7
400 79800.0 40089.3 2281.2
600 179700.0 89819.1 7328.1
800 319600.0 159787.6 17083.3
1200 719400.0 358853.3 56375.0
1600 1279200.0 642036.1 135791.7

整列させるリストは前回と同じなので交換回数は全く変わっていない。
処理の打ち切りは整列が終わらない限り行われず、
整列のための交換回数は打ち切りうんぬんとは無関係だからである。
途中での打ち切りがないため比較回数は要素数 $n$ に対して常に $\frac{n(n-1)}{2}$ 回となる。
とはいえ打ち切りの効果が顕著に現れるような最良ケースに近いリストが作成されることはあまりないので、
前回の比較回数の結果はほんの少しだけ少ないとはいえ今回の結果とほとんど同じである。
交換処理が支配的であろうため、処理に要するCPU時間も前回とほとんど変わらなかった。

与えられるリストが処理を早めに打ち切れるようなものが多いことが分かっているなら、
打ち切り処理を組み込んだものは効果を発揮するだろうが、
そうでなければ効果はほとんど望めないだろう。