sewe
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

In the exercise we found that bubbling up the minimum value already happens in O(n) in the implementation that was part of assignment 5, task 6. However, distributing the merges among the various sublists was too expensive, thanks to length, take, and drop: O(n log n). The following implementation avoids this, however:

Code: Alles auswählen

mMin = head . mSort

mSort :: Ord a => [a] -> [a]
mSort []  = []
mSort xs  = foldtree1 merge (map (:[]) xs)

merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) =
if x <= y then x:merge xs (y:ys) else y:merge (x:xs) ys

foldtree1 :: (a -> a -> a) -> [a] -> a
foldtree1 f [x] = x
foldtree1 f xs  = foldtree1 f (pairs xs)
where
pairs []        = []
pairs [x]       = [x]
pairs (x:x':xs) = f x x' : pairs xs
Just play around a little bit with foldtree1 to understand what it does.