www.jammni.de

Logo - Kleiner Drache
Login
Username:

Passwort:

Daten merken
Auto-Login
Registrieren
 
Online
niemand
 
Forumsuche
Suche nach:

Logo - DracheHaskell-Forum

vorherige Seite 1 2  

Landei

Gepostet:
08.07.2013 23:43

   
Ein paar Tricks, die mir so bei Merge-Sort eingefallen sind:


sort xs@(_:_:_) = merge $ map sort $ split xs
sort xs = xs

split = foldr (\x [l,r] -> [x:r,l]) [[],[]]

merge [x:xs,y:ys]
| x < y = x : merge [xs, y:ys]
| otherwise = y : merge [x:xs, ys]
merge xss = concat xss


In sort arbeite ich mit einer zwei-elementigen Liste statt einem Paar, damit kann ich "map sort" schreiben. Das Pattern xs@(_:_:_) stellt sicher, dass ich mindestens zwei Elemente in der Liste habe. Damit kann ich danach den null- und ein-elementigen Fall zusammen abhandeln.

Die split-Funktion hatte ich oben schon als splitInHalves erwähnt (einzige Änderung ist wieder die zwei-elementige Liste statt einem Paar).

In merge habe ich die Fälle, dass mindestens eine der Listen leer ist, zusammengefasst. Die zwei-elementige Liste hat den Vorteil, dass ich einfach concat aufrufen kann, ohne die Einzelteile kennen zu müssen.
Zum Seitenanfang    
 

vorherige Seite 1 2