Tutorial by Examples

insert :: Ord a => a -> [a] -> [a] insert x [] = [x] insert x (y:ys) | x < y = x:y:ys | otherwise = y:(insert x ys) isort :: Ord a => [a] -> [a] isort [] = [] isort (x:xs) = insert x (isort xs) Example use: > isort [5,4,3,2,1] Result: [1,2,3,4...

Ordered merging of two ordered lists Preserving the duplicates: merge :: Ord a => [a] -> [a] -> [a] merge xs [] = xs merge [] ys = ys merge (x:xs) (y:ys) | x <= y = x:merge xs (y:ys) | otherwise = y:merge (x:xs) ys Top-down version: msort :: Ord a => [...

qsort :: (Ord a) => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort [a | a <- xs, a < x] ++ [x] ++ qsort [b | b <- xs, b >= x]

bsort :: Ord a => [a] -> [a] bsort s = case bsort' s of t | t == s -> t | otherwise -> bsort t where bsort' (x:x2:xs) | x > x2 = x2:(bsort' (x:xs)) | otherwise = x:(bsort' (x2:xs)) bsort' s = s

Also known as bogosort. import Data.List (permutations) sorted :: Ord a => [a] -> Bool sorted (x:y:xs) = x <= y && sorted (y:xs) sorted _ = True psort :: Ord a => [a] -> [a] psort = head . filter sorted . permutations Extremely inefficient (on today's compu...

Selection sort selects the minimum element, repeatedly, until the list is empty. import Data.List (minimum, delete) ssort :: Ord t => [t] -> [t] ssort [] = [] ssort xs = let { x = minimum xs } in x : ssort (delete x xs)