単連結リストの整列 #75 三次のオーダになるのは必至ではない

所要時間が要素数の三次のオーダになるのは、
整列機能がリストに求める交換処理機能が任意の要素二つを指定しての交換であるからである。
その場合、一つ前の要素を得るという処理が必須であり、
リストを先頭方向にたどることができないという純粋な単連結リストであるならば、
一つ前の要素を得るための処理時間は要素数の一次オーダにならざるを得ず、
要素数の二次オーダの交換回数が必要な整列処理全体では処理時間は要素数の三次オーダとなってしまう。

したがって、例えば任意の要素の次の要素とさらに次の要素とを交換する機能があれば十分な隣接交換法に特化すれば、
この交換機能は単連結リストであっても要素数に関して定数時間で終了するため、
整列処理全体として処理時間は要素数の二次オーダになる。
ただし、機能による単連結リストの表現をこのようにした場合は、
先頭要素の一つ前の要素の指定をどう表現するかという問題や、
挿入法などの隣接交換法以外の整列法に変えるといったことができなくなってしまう問題など、
インタフェイスにまつわる問題が出てくる。

汎用性と効率性とはトレードオフの関係にあり悩ましい問題だ。