Sorting algorithms/Bubble sort: Difference between revisions

This version is based on the above, but avoids sorting whole list each time. To implement this without a counter and retain using pattern matching, inner sorting is reversed, and then result is reversed back. Sorting is based on a predicate, e. g. (<) or (>).

<lang haskell>import Data.Maybe (fromMaybe)

import Control.Monad

bubbleSortBy :: (a -> a -> Bool) -> [a] -> [a]

bubbleSortBy f as = case innerSort $ reverse as of

Nothing -> as

Just v -> let (x:xs) = reverse v

in x : bubbleSortBy f xs

where innerSort (a:b:cs) = if b `f` a

then liftM (a:) $ innerSort (b:cs)

else Just $ b : fromMaybe (a:cs)

(innerSort $ a:cs)

innerSort _ = Nothing

bsort :: Ord a => [a] -> [a]

bsort = bubbleSortBy (<)</lang>