--------------------
-- Sample sorting algorithms
-- Fritz Ruehr, WU CS 454, Spring 03
-------------------
--------------------
-- Type signatures for sort functions
-- (note: not the generic versions yet)
isort, ssort, ssort', msort, msort', qsort, qsort', tsort, tsort' {-, hsort -}
:: Ord a => [a] -> [a]
--------------------
-- Insertion sort [easy split, hard join; one and many]
--------------------
isort [] = []
isort (x:xs) = ins x (isort xs)
ins a [] = [a]
ins a (b:bs) = if a <= b then a:b:bs
else b:ins a bs
--------------------
-- Selection sort [hard split, easy join; one and many]
--------------------
ssort [] = []
ssort xs = m : ssort (xs \\ m)
where m = minimum xs
[] \\ x = []
(a:as) \\ x = if a==x then as
else a: (as \\ x)
-- using a tupling technique for minimum
ssort' [] = []
ssort' (x:xs) = m : ssort' (rest)
where (m,rest) = minl (x,xs)
minl (m,[]) = (m,[])
minl (m,x:xs) = if m <=x then let (n,ys) = minl (m,xs) in (n,x:ys)
else let (n,ys) = minl (x,xs) in (n,m:ys)
--------------------
-- Merge sort [easy split, hard join; half and half]
--------------------
msort [] = []
msort [x] = [x]
msort xs = merge (both msort (split xs))
split (x:y:rest) = each (x:) (y:) (split rest)
split xs = (xs,[])
merge (xs,[]) = xs
merge ([],ys) = ys
merge (x:xs,y:ys) = if x=x]
-- using accumulation
qsort' [] = []
qsort' xs = qs xs []
where qs [] acc = acc
qs (x:xs) acc = qs as (x : qs bs acc)
where (as,bs) = partition ( [ [a] -> [a] ]
sorts = [ isort, ssort, msort, qsort ]
check = and [sort t == r | sort<-sorts, (t,r) <- zip tests results]
-- generating interesting larger tests
test2 = test ++ test
grow test = concat (trans (tab (\i j->i*10+j) test test))
big = grow test
bigger = grow test ++ grow test
tab f xs ys = map (flip map ys . f) xs
trans [] = []
trans [xs] = map (:[]) xs
trans (xs:xss) = zipWith (:) xs (trans xss)
{- --------------------
Speed comparisons
--------------------
algm test test2 big bigger
----- ---- ----- ----- ------
isort 364 1184 25735 100985
ssort 730 2684 63316 251471
ssort' 672 2532 60612 241212
msort 321 809 5733 13080
msort' 319 732 5158 11748
qsort 508 1300 10516 24430
qsort' 317 755 5597 12721
tsort 374 913 6923 15881
tsort' 355 865 6595 15125
-------------------- -}