[ create a new paste ] login | about

Link: http://codepad.org/7zYH7BJ8    [ raw code | output | fork ]

edvakf - Haskell, pasted on Nov 30:
insertionSort :: (Ord a) => [a] -> [a]
insertionSort [] = []
insertionSort (x:xs) = insertionSort' [x] xs

insertionSort' :: (Ord a) => [a] -> [a] -> [a]
insertionSort' os [] = os
insertionSort' os us = insertionSort' os'' us''
    where
        (os', us', olast) = separateSorted us -- olast : last (rightmost) of os'
        (ls, us'') = span (< olast) us'  -- ls : all less than olast, us'' : unordered (head us'' >= olast)
        os'' = insertAll (os++os') ls

separateSorted :: (Ord a) => [a] -> ([a], [a], a)
separateSorted xs@(x:[]) = (xs, [], x)
separateSorted xs@(x:xs'@(x':_))
    | x <= x'   = (x:os, us, m)
    | otherwise = ([x], xs', x)
        where
            (os, us, m) = separateSorted xs'

insertAll :: (Ord a) => [a] -> [a] -> [a]
insertAll os [] = os
insertAll os (l:ls) = insertAll (insert os l) ls

insert :: (Ord a) => [a] -> a -> [a]
insert os u = ls ++ (u:hs)
    where
        (ls, hs) = span (< u) os -- span lows and highs

main = print $ insertionSort [3,4,5,3,2,1,4]


Output:
1
[1,2,3,3,4,4,5]


Create a new paste based on this one


Comments: