すごいH本 part14

クイックソートを実装する

ソートアルゴリズムはこんな感じ

リストから任意の数を選ぶ(この数字をピボットと呼ぶ)
ピボットより大きい数字を右側に、ピボット以下の数字を左側に移動する
ピボットを除いた左右のリストに対して、1. 2. の手順を繰り返していく

実装

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerOrEqual = [a | a <- xs, a <= x]
        larger = [a | a <- xs, a > x]
    in  quicksort smallerOrEqual ++ [x] ++ quicksort larger

実行結果

*Main> quicksort [2,5,8,1,3,0]
[0,1,2,3,5,8]

再帰で考える

基底部を見つける
部分問題を再帰的に解く

この2つを正しく選んだなら全体として何が起こるかの詳細を考える必要がない。

所感

中学生レベルの数学の知識しかないが、演繹的というのだろうか。理論が先にあってそれが広がっているという感じで処理を書いていく感覚が得られた。まず、問題を分解していくというところでつまづくと何も始まらないという難しさも同時にあるように思える。最初の章に書いてあったが、Haskell はエレガントであるというところの意味が少しわかった。もうすでに問題は解けている。自明である。このような美しさがあるように感じた。

今日はここまで。