quick-sort with ridiculous pivot

Haskellを使って、シンプルにクイックソートを記述します。

クイックソートのアルゴリズムは、基準となる値（ピボット）と比較して、

小さな集合、大きな集合を選別、選別した集合毎に、再度、ピボットを選び、

小さな集合、大きな集合を選別するといったシンプルなもの。

今回は、リストの先頭要素を、基準値として集合を選別します。

シンプルというからには、再帰を使うのですが、まずは昇順クイックソート。

quick-sort.hs

qsort :: (Ord a) => [a] -> [a]

qsort [] = []

qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger

where

smaller = [a | a <- xs, a <= x]

larger = [b | b <- xs, b > x]

んで、次は降順クイックソート。

quick-sort2.hs

qsort :: (Ord a) => [a] -> [a]

qsort [] = []

qsort (x:xs) = qsort larger ++ [x] ++ qsort smaller

where

smaller = [b | b <- xs, b < x]

larger = [a | a <- xs, a >= x]

ピボットの選択方法は、この場合、不適切なのですが、仮に適切なピボットを

選ぶ実装をしても、Cや、Javaといった命令型言語と比べて圧倒的に少ないコーディング量で

実現出来るでしょー。