Haskellで遊ぶよ

Bubble Sort

03:59

bubbleSort :: Ord a => [a] -> [a]
bubbleSort = bubbleSortBy compare

bubbleSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a]
bubbleSortBy _ [] = []
bubbleSortBy cmp xs = y : (bubbleSortBy cmp (reverse ys))
    where 
        (ys, y) = bubbleBy cmp xs

bubbleBy :: Ord a => (a -> a -> Ordering) -> [a] -> ([a], a)
bubbleBy _ [x] = ([], x)
bubbleBy cmp (x:xs@(x':xs')) = if cmp x x' == GT
    then let (ys, y) = bubbleBy cmp xs      in (x:ys, y)
    else let (ys, y) = bubbleBy cmp (x:xs') in (x':ys, y)

main = print $ bubbleSort [4,5,6,3,1,3,2,5,8,4,3,2]

よく見るバブルソートとちょっと違って、バブルして最後に残るやつが最大値ではなく最小値になっている。

ググってもあまりよさそうなのがなかった。

↑の bubbleBy はこれでもいい。ちょっとは分かりやすいか。

bubbleBy _ [x] = ([], x)
bubbleBy cmp (x:xs) = foldl takeSmall ([], x) xs
    where
        takeSmall (ys, y) z = if cmp y z == GT  
            then (y:ys, z) 
            else (z:ys, y)

foldl じゃなくて foldr にしたら reverse が要らなくなるな。しかし大きなリストだと stack overflow になる可能性が。