Mergesort#

Elm heeft een ingebouwde functie voor het sorteren van een lijst. Kijk maar: het resultaat van List.sort aList is een lijst met dezelfde waarden als in aList, maar nu geordend.

import List exposing (sort, take, drop, reverse, length, range)



List.sort [7,3,8,6,8,5,4,5,3,6,2,6,9,1,2,7,5,8,7,6]

[1,2,2,3,3,4,5,5,5,6,6,6,6,7,7,7,8,8,8,9]
    : List number

Je gaat nu zelf een sorteerfunctie maken, mergesort, gebaseerd op het merge sort algoritme. Het basisidee van de merge hierin is het volgende:

  • als je twee gesorteerde lijsten a en b hebt, maak je daaruit een gesorteerde lijst door steeds de eerste elementen van a en b te vergelijken;

  • stel dat het kleinste k op kop van a staat:

  • zet k op de kop van de merge van b en de rest van a.

Maak nu eerst de functie voor het “mergen” van twee lijsten a en b.

Tip: gebruik de case constructie met het tupel (a,b), en de gevallen ([],_), (_,[]), en (x::xs, y::ys).

merge : List Float -> List Float -> List Float
merge a b = []

<function> : List Float -> List Float -> List Float

merge [1,2,3] [2,3,4]

[] : List Float

Merge sort#

Hoe kun je nu een lijst sorteren?

  • splits de lijst in twee (bijna) even grote deellijsten

  • sorteer deze deellijsten

  • “merge” de deellijsten tot een gesorteerde lijst

Dit is een recursief schema: voor het sorteren van een lijst heb je een functie nodig voor het sorteren van een (kortere) lijst. Hiervoor kun je weer dezelfde mergesort functie gebruiken!

Voor het splitsen van een lijst lst in twee (bijna) gelijke lijsten gebruik je de functies List.take en List.drop, met als eerste parameter de helft van de lengte van lst.

take 2 [1,2,3,4]

[1,2] : List number

drop 2 [1,2,3,4]

[3,4] : List number

Definieer de functie mergesort, met behulp van de eerder gedefinieerde functie merge.

Vraag: wat is het resultaat als de lijst te kort is om in 2 lijsten te splitsen?

mergesort : List Float -> List Float
mergesort lst = []

<function> : List Float -> List Float

mergesort [7,3,8,6,8,5,4,5,3,6,2,6,9,1,2,7,5,8,7,6]

[] : List Float

Een andere splits#

In plaats van take en drop kun je ook een recursieve functie maken voor het splitsen van een lijst in twee (bijna) even lange lijsten.

De functie split lst left right splitst de lijst lst in twee lijsten, door steeds de kop-elementen van lst toe te voegen aan left en right. Als lst leeg is, vormen left en right het resultaat.

Vraag: wat is het resultaat als lst uit 1 element bestaat?

split : List Float -> List Float -> List Float -> (List Float, List Float)
split lst lsta lstb = ([], [])

<function>
    : List Float -> List Float -> List Float -> ( List Float, List Float )

Voor het splitsen van een lijst gebruiken we de functie split, met de te splitsen lijst, en twee extra parameters: de tussenresultaten van het splitsen. Als de te splitsen lijst nog ten minste twee elementen heeft, voegen we het ene kopelement toe aan de ene split-lijst, en het andere kopelement aan de andere split-lijst. Als de lijst korter is, zijn we (bijna) klaar: het resultaat bestaat uit de beide split-lijsten.

Deze techniek van het gebruik van extra parameters voor het opbouwen van een resultaat kom je vaker tegen bij recursieve programma’s. Je kunt dit vergelijken met het gebruik van extra variabelen in een sequentieel algoritme.

split [] [] []

([],[]) : ( List Float, List Float )

split [1] [] []

([],[]) : ( List Float, List Float )

split [1,2] [] []

([],[]) : ( List Float, List Float )

split [1,2,3,4,5,6,7,8,9] [] []

([],[]) : ( List Float, List Float )

Definieer mergesort1 met behulp van deze functie split.

mergesort1 : List Float -> List Float
mergesort1 lst = []

<function> : List Float -> List Float

mergesort1 [7,3,8,6,8,5,4,5,3,6,2,6,9,1,2,7,5,8,7,6]

[] : List Float