Skip to content

Instantly share code, notes, and snippets.

@meikj
Last active January 3, 2016 03:19
Show Gist options
  • Save meikj/8401622 to your computer and use it in GitHub Desktop.
Save meikj/8401622 to your computer and use it in GitHub Desktop.
-- Insertion sort
inssort :: Ord a => [a] -> [a]
inssort [] = []
inssort (x:xs) = insert x (inssort xs)
where
insert :: Ord a => a -> [a] -> [a]
insert n [] = [n]
insert n (x:xs)
| n <= x = n : x : xs
| otherwise = x : insert n xs
-- Insertion sort (higher order version)
inssortBy :: Ord b => (a -> b) -> [a] -> [a]
inssortBy f [] = []
inssortBy f (x:xs) = insertBy f x (inssortBy f xs)
where
insertBy :: Ord b => (a -> b) -> a -> [a] -> [a]
insertBy f n [] = [n]
insertBy f n (x:xs)
| f n <= f x = n : x : xs
| otherwise = x : insertBy f n xs
-- Quicksort
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort (less x xs) ++ occs x (x:xs) ++ qsort (more x xs)
where
less n xs = [x | x <- xs, x < n]
occs n xs = [x | x <- xs, x == n]
more n xs = [x | x <- xs, x > n]
-- Quicksort (higher order version)
qsortBy :: Ord b => (a -> b) -> [a] -> [a]
qsortBy f [] = []
qsortBy f (a:xs) = qsortBy f less ++ occs ++ qsortBy f more
where
less = [x | x <- xs, f x < f a]
occs = a : [x | x <- xs, f x == f a]
more = [x | x <- xs, f x > f a]
-- Merge sort
msort :: Ord a => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort ys) (msort ws)
where
(ys,ws) = (take l xs, drop l xs)
l = length xs `div` 2
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = if x < y then x : merge xs (y:ys) else y : merge (x:xs) ys
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment