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といった命令型言語と比べて圧倒的に少ないコーディング量で
実現出来るでしょー。