Assignment 5, Task 6: O(n) implementation of (head . mSort)

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

Assignment 5, Task 6: O(n) implementation of (head . mSort)

Beitrag von sewe »

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.

Zurück zu „Archiv“