クイックソート

「プログラミング Haskell」の第１章に、次の定義のクイックソートが出てくる。

qsort []     = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
               where
                smaller = [a | a ← xs, a ≦ x]
                larger  = [b | b ← xs, b ＞ x]

この章の例題を解いていて気が付いたんだけれど、このソート、安定 (stable) ではない。
同じ値をもつリストをソートすると、結果のリストでは、値の出てきた順序がひっくり返る。　たとえば [1,2,1,1] をソートした結果は [1,1,1,2] になるものの、結果のリストの先頭の 1 は、ソート前のリストの最後の 1 である。　（というのは smaller のリストを作る条件に等号が入っているため。　等号を larger の側に移せば stable ソートになる）

で、これを具体的にみるために、ソートするリストを、その要素にリスト中の位置をタプルとして組み込んでみせればよいと考えた。　つまり [1,2,1,1] を [1..] と zip した [(1,1), (2,2), (1,3), (1,4)] をソートしてみせればよい。　(≦ をつかってソートすると結果は [(1,4), (1,3), (1,1), (2,2)] となる)

ただ、タプルに対して定義される比較演算子をそのまま使うと、 (1,1) と (1,3) に対して明示的な大小関係ができてしまうので、この目的では使えない。
smaller や larger の部分列を計算する式中の比較演算子を、外部から注入できるように定義を書き換える必要がある。

qsort' _ []     = []
qsort' f (x:xs) = qsort' f smaller ++ [x] ++ qsort' f larger
               where
                smaller = [a | a ← xs, a `f` x]
                larger  = [b | b ← xs, not (b `f` x)]

ちょっとわかりにくくなったけれど、 qsort' (<=) と qsort は同じ関数だ。

これで役者はそろったので実験してみよう。

*Main> qsort (\(x,_) (y,_) -> x <= y) (zip [1,2,1,1] [1..])
[(1,4), (1,3), (1,1), (2,2)]

念のため。

*Main> qsort (\(x,_) (y,_) -> x < y) (zip [1,2,1,1] [1..])
[(1,1), (1,3), (1,4), (2,2)]

ついでに。

*Main> qsort (<=) [1,2,1,1]
[1,1,1,2]

蛇足

リスト内包表記で定義している smaller と larger は、 List モジュールに定義されている partition でひとまとめに計算できる。

import List
qsort' _      []     = []
qsort' lesser (x:xs) = qsort' lesser ss ++ (x : qsort' lesser ls)
  where (ss, ls) = partition (`lesser` x) xs