ここでは、Haskellでクイックソート(quick sort)を実装してみましょう。 クイックソートを知らない人は このページ を参照してください。 Haskell による典型的なクイックソートの実装は以下のようになるでしょう。
この実装は Haskell の入門などでよく紹介されますが、
実は重大な問題があります。
ソート済みの系列をソートすると \(O(n^2)\) の計算量がかかるのです。
ソート済みの系列をソートすることはありがちな局面なので、
これでは全く実用性がありません。
また、lhs と rhs
は本来一回のリストの走査で計算できるのに、
２回に分けて求めている所も効率が悪いです。
そこで、pivot の選び方を工夫してソート済みの系列に対しても \(O(n\log n)\) の計算量になるように修正し、 リストの不要な走査もでき得るかぎり減らすと、以下のようになります。 系列の先頭・中間・末尾の３つの中の中央値を pivot として選びます。
ただし、このように工夫してもなお、
巧妙に工夫された系列では \(O(n^2)\)
の計算量がかかることが知られています。
ところで、クイックソートは一般に不安定なソートとして知られていますが、
QuickSort1.hs, QuickSort2.hs の実装は安定なソートです。
QuickSort2.hs では lhs, rhs だけではなく、
pivot に等しい要素を pivots として系列を３分していますが、
これにより、このソートは安定ソートになります。
上記の QuickSort2.hs は (++) 演算子を濫用しており、
まだまだ効率が悪いです。また、
山型の系列を処理すると計算量が \(O(n^2)\) になります。
そこで、より実用性を考慮すると以下のようになります。
QuickSort3.hs も安定ソートです。
以下のような qcat 関数が何やら素直じゃありませんが、
これは関数型言語で２分木処理をする時の定石なんだそうです。
qcat _ ![] ys = ys
qcat !n !xs ys = qcat nl (lhs []) (pivots !++ qcat nr (rhs []) ys)
言われてみれば、クイックソートは２分木処理の一種ですね。
こう書くと、
素朴に書いた場合に (++) 演算子の繰り返しの最悪計算量が
\(O(n^2)\) になるのが \(O(n)\) に抑えられるそうです。
関数脳って面倒くさいなぁ...
ちなみに、ボトムアップマージソートのページ
で説明した、リストの末尾への要素の追加の計算量を
\(O(1)\) に抑えるテクニックも使っています。
このコードの高速化のミソはこれ以外に pseudoMedian
関数があります。これは多くの場合に与えられた系列のほぼ中央値を返します。
そのため典型的なケースでは２分木の分割がほぼ半々になり、
再帰の深さが理想値に近づきます。
クイックソートが遅くなるのは、２分木分割のバランスが崩れて、
再帰の深さが深い部分ができてしまうことが原因ですので、
この関数を導入すると性能が改善されます。
pseudoMedian 関数を使うと、
昇順・降順・山型などの系列を与えても、
計算量が \(O(n^2)\) になったりしません。
一応、クイックソートキラー(quick sort killer)として知られる
クイックソートを \(O(n^2)\)
の最悪計算量に陥れるテストにかけてみましたが、
マージソートなどと変わらない効率を維持していました。
(クイックソートキラーに関しては
こちらのページ
へどうぞ)
この他にも、median of medians という方法があるそうですが、 何やら面倒くさそうだし、サンプルコードも見当たらないのであきらめました。 median of medians の場合、 pivot による分割が最悪でも 30% : 70% で行われるそうで、 より２分木分割が理想に近づくそうですが、 実際にはそこまでやる必要はないようです。
上記の pseudoMedian 関数は最悪の pivot
を選ぶことがあります。
つまり、２分木の分割が \(1 : n - 1\) になることがあります。
しかし、クイックソートが \(O(n^2)\) の計算量に陥るのは、
最悪の選択が \(n\) に比例するくらいある場合です。
最悪の選択が \(\log n\) に比例するくらいに抑えられていれば、
計算量は \(O(n\log n)\) に抑えられます。
pseudoMedian 関数はその条件を満たしています。