単連結リストの整列 #82 降順列と昇順列の昇順整列

単連結リストを双方向連結リストに書き換えたときと同じで、
整列関数listsortのインタフェイスを変えたわけではないため、
今まで作ってきたlistsortを利用するコードはそのまま使える。
例によって、#65のコードをlistsort-s.cのオブジェクトとリンクすると、

10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10
#comparisons=45, #swaps=5
1 2 3 4 5 6 7 8 9 10
#comparisons=45, #swaps=0

となる。この結果は単連結なintlistでも双方向連結なintdlistでも同じになる。
比較回数は途中打ち切りなしの隣接交換法と同じであり、
#69の最後の結果と同様に降順→昇順でも昇順→昇順でも要素数10に対して45回である。

注目すべきは交換回数であり、5回の交換で済んでいる。
隣接交換法での降順→昇順という最悪ケースでは45回の交換が必要なのに対して劇的に少なくなっている。
しかし、基本選択法では最低順位の要素を探索するループが、要素数より一回分少ない回数だけ実行され、
このループ一回につき最大一回の交換が行われるので、
基本選択法における最悪ケースの交換回数は9回となるはずである。
これは、隣接交換法における最悪ケースと基本選択法における最悪ケースとが一致しないという単純な理由である。
つまり降順に並んでいると一回の交換で順位の一番低い要素が前に、順位の一番高い要素が後に移動するため、
リストの半分まで整列が進んだ時点で整列完了状態になり、要素数の半分の回数の交換で整列ができてしまう。
したがって基本選択法での昇順整列にとって降順に並んでいるものは交換回数に関する最悪ケースとはならない。

比較回数について、隣接交換法では繰り返し処理一回分の間に一回の交換も行われなかった場合、
リスト全体の整列が終了したことになるので、その時点で処理を打ち切ることができる。
しかし、基本選択法では途中で打ち切ってもよいという条件がないため、処理は最後まで行わなければならない。
このため、比較回数は途中での打ち切り無しの隣接交換法と同じ回数が必要となる。