続・クイックソート

そういえば、同じ値がたくさん入っている列をソートするときに、先日の partition をつかった実装だと、再帰呼び出しのなかで再度おなじ値の比較が走ることになって比較コストがばかにならないなあ…　とおもった。
strcmp のように、一回の比較で同じか、小さいか、それとも大きいかを決定できる場合、同じ値を再帰ソートにまわさないようにすれば効率が上がるだろう。　…ってんで、ちょいと書き直してみた。：

data Ordinal = LessThan | EqualsTo | GreaterThan

qsort :: (a -> a -> Ordinal) -> [a] -> [a]
qsort _ [] = []
qsort compare (x:xs) = qsort compare ls ++ (x:es) ++ qsort compare gs  where
      (ls, es, gs) = partition3 compare x xs

partition3 :: (a -> a -> Ordinal) -> a -> [a] -> ([a], [a], [a])
partition3 compare x vs = aux vs ([], [], [])  where
           aux []     result       = result
           aux (v:vs) (ls, es, gs) = case compare v x of
               LessThan    -> aux vs (ls++[v], es, gs)
               EqualsTo    -> aux vs (ls, es++[v], gs)
               GreaterThan -> aux vs (ls, es, gs++[v])

ここでたとえば次のような比較関数を定義して、…

compar :: Ord a => a -> a -> Ordinal
compar x y = case (x < y, x <= y) of
       (True, _) -> LessThan
       (_, True) -> EqualsTo
       otherwise -> GreaterThan

先の qsort に渡すと、…

*Main> qsort compar [1,2,1,1,2]
[1,1,1,2,2]

と、ソートができる。