先日は挿入ソートについて考えたが、今日はクイックソートについて考える。 今回もHaskellでの実装を念頭に置いて、まずRubyでクイックソートを実装する。
クイックソートの基本的な仕組みは以下のとおりだ。
- リスト中で要素のある数より大きな要素と小さな要素を分ける(便宜的にこれを
qsortの処理とする) - 大きな要素に対し、
qsortを再帰的に適用する - 小さな要素に対し、
qsortを再帰的に適用する
今回のRubyの実装では、クイックソートを3パートに分けて実装する。
- クイックソートの本体処理である
qsort - リストからある数より小さな要素を抜き出したリストを作る
smaller - 同様に大きな要素を抜き出したリストを作る
larger
以上を踏まえたソースコードは以下のとおり。
def qsort(list)
if list.length > 0
x = list[0]
xs = list[1..-1]
qsort(smaller(x, xs)) + [x] + qsort(larger(x, xs))
else
[]
end
end
def smaller(x, list)
let = list.select{|a| a <= x}
end
def larger(x, list)
let = list.select{|b| b > x}
end
p qsort([4, 1, 3, 2, 5])
[1, 2, 3, 4, 5]
これをHaskellで実装する。 関数名や変数名は可能な限りRubyの実装にあわせている。 ポイントはsmallerとlargerで使っているリスト内包表記による絞り込みだろう。
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = (qsort (smaller x xs)) ++ [x] ++ qsort((larger x xs))
smaller :: Ord a => a -> [a] -> [a]
smaller x xs = [a | a <- xs, a <= x]
larger :: Ord a => a -> [a] -> [a]
larger x xs = [b | b <- xs, b > x]
main = do
print $ (qsort [4, 1, 3, 2, 5])
[1,2,3,4,5]
これでも動作するが、この書き方は少し冗長だ。 smallerとlargerはqsort内だけで使用される関数だ。 そこでwhereを使ってqsort内でこれらの関数を定義してやると、以下のようになる。
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]
main = print $ (qsort [4, 1, 3, 2, 5])
結果、Haskellではわずか6行でクイックソートを実装することができた。ループを再帰として捉えること、リストの操作をリスト内包表記で行うこと、これらにだんだん慣れてきた。
Haskellでのクイックソートの実装については、プログラミングHaskellの6.4 多重再帰の項を参考にした。説明が丁寧な良書である。
