-------------------- -- 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 -------------------- -}