[ create a new paste ] login | about

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

edvakf - Haskell, pasted on Dec 4:
import List

-- shell sort
shellSort :: Ord a => [a] -> [a]
shellSort = shellSortBy compare

shellSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a]
shellSortBy _ [] = []
shellSortBy _ [x] = [x]
shellSortBy cmp [x,y] = if cmp x y == GT then [y,x] else [x,y]
-- do insertion sort if list is short
shellSortBy cmp xs@([x1,x2,x3]) = insertionSortBy cmp xs
shellSortBy cmp xs@([x1,x2,x3,x4]) = insertionSortBy cmp xs
shellSortBy cmp xs@([x1,x2,x3,x4,x5]) = insertionSortBy cmp xs
shellSortBy cmp xs@([x1,x2,x3,x4,x5,x6]) = insertionSortBy cmp xs
shellSortBy cmp xs@([x1,x2,x3,x4,x5,x6,x7]) = insertionSortBy cmp xs
shellSortBy cmp xs@([x1,x2,x3,x4,x5,x6,x7,x8]) = insertionSortBy cmp xs
shellSortBy cmp xs@([x1,x2,x3,x4,x5,x6,x7,x8,x9]) = insertionSortBy cmp xs
-- else split into 3 
shellSortBy cmp xs = insertionSortBy cmp $ merge3 (shellSortBy cmp as) (shellSortBy cmp bs) (shellSortBy cmp cs)
    where 
        (as,bs,cs) = split3 xs

split3 :: [a] -> ([a], [a], [a])
split3 [] = ([],[],[])
split3 [x] = ([x],[],[])
split3 [x,y] = ([x],[y],[])
split3 (a:b:c:xs) = (a:as, b:bs, c:cs)
    where 
        (as, bs, cs) = split3 xs

merge3 :: [a] -> [a] -> [a] -> [a]
merge3 [] [] [] = []
merge3 [x] [] [] = [x]
merge3 [x] [y] [] = [x,y]
merge3 (x:xs) (y:ys) (z:zs) = x:y:z:(merge3 xs ys zs)

-- insertion sort
insertionSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a]
insertionSortBy cmp [] = []
insertionSortBy cmp (x:xs) = insertBy cmp x $ insertionSortBy cmp xs

main = print $ shellSort [23,4,5,43,6,3,2,94,3,2,63,68,95,33,22,67,4,2,67,47,89,53,26,83,56,78,96,4,32,12,45,67,45,3,68,94,21,56,7,85,3,21,6,83,24,79,34,23,32,76,54,1,24,64,98,62,19,63,28,36,18,52]


Output:
1
[1,2,2,2,3,3,3,3,4,4,4,5,6,6,7,12,18,19,21,21,22,23,23,24,24,26,28,32,32,33,34,36,43,45,45,47,52,53,54,56,56,62,63,63,64,67,67,67,68,68,76,78,79,83,83,85,89,94,94,95,96,98]


Create a new paste based on this one


Comments: