Les 4 - Mergesort

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

MergeSort

Leerdoel

Aan het eind van deze les ken je het principe van het MergeSort algoritme en kan je elementen uit een lijst sorteren aan de hand van het MergeSort algoritme.

Sorteer de volgende lijst met elementen in de juiste volgorde van klein naar groot volgens het Bubblesort algoritme. Gebruik het stappenplan

4-1-9-8-5

Het BubbleSort algoritme moet de hele lijst doorlopen om te controleren of het klaar is met sorteren.

1. Juist
2. Onjuist

Geef een lijst met 5 elementen (getallen) waarin sprake is van een worstcasescenario bij BubbleSort

Hoe zou je dit oplossen?

“Stel er is brand in de school en iedereen moet naar buiten. Om er zeker van te zijn dat iedereen buiten is moet je tellen hoeveel leerlingen op het schoolplein staan. Je kunt dan de leerlingen één voor één gaan tellen. Bij een school met honderden leerlingen kost dat veel tijd, de school is dan al lang afgebrand. Is er niet een slimmere, snellere manier om dat te doen?”

Zou dit werken?

Is dit sneller dan 1 voor 1 tellen?

Ja, natuurlijk!

Stel, je hebt 30 leerlingen

Na 1x getal uitwisselen staan er nog 15 leerlingen

Na 2x getal uitwisselen staan er nog 8 leerlingen

Na 3x getal uitwisselen staan er nog 4 leerlingen

Na 4x getal uitwisselen staan er nog 2 leerlingen

Na 5x getal uitwisselen staat er nog 1 leerling

Hoe zou je dit oplossen?

"Een docent heeft van twee klassen de antwoorden van een toets. Per klas zijn de antwoorden gesorteerd op alfabetische volgorde van de achternaam van de leerlingen. De docent wil deze twee stapels samenvoegen tot één stapel."

Antwoord

Het makkelijkst is als de docent een derde stapel maakt. Hierbij kijkt hij steeds naar de eerste twee stapels. Het exemplaar met de alfabetisch opvolgende naam legt hij op de nieuwe stapel. Als de twee stapels 'op' zijn, is de derde stapel correct op alfabet gesorteerd.

MergeSort

In de voorgaande oefeningen was er spraken van een zogenaamde divide-and-conquermethode (verdeel-en-heersmethode). 

Soms is een probleem te groot om direct op te lossen. De divide-and-conquermethode splitst een probleem op in kleinere deelproblemen. Deze deelproblemen worden eerst opgelost. Daarna wordt de oplossing van alle deelproblemen samengevoegd tot de totaaloplossing van het probleem.

Divide-and-conquermethode

De divide-and-conquermethode bestaat uit 3 stappen:

• Divide: verdeel het probleem in kleinere deelproblemen
• Conquer: los de deelproblemen op. Lukt dat niet? Verdeel de deelproblemen dan in nog kleinere deelproblemen.
• Combine: voeg de oplossingen van de deelproblemen samen,

Divide-and-conquermethode

Getallen sorteren met MergeSort

4         3         5         9         3        1         6

Getallen sorteren met MergeSort

Oefenen!

Sorteer de volgende lijst met elementen met behulp van het MergeSort algoritme. Schrijf de tussenstappen uit.

5 9 5 2 1 9 5

En nog een keer oefenen!

Sorteer de volgende lijst met elementen met behulp van het MergeSort algoritme. Schrijf de tussenstappen uit.

9 1 6 3 9 8 3 6 2

Wat bepaalt in de verdeelfase van MergeSort het aantal stappen dat je moet nemen?

1. De mate waarin de lijst al gesorteerd is.
2. Het aantal elementen van de lijst.
3. De hoeveelheid dezelfde elementen in de lijst.
4. In hoeverre de lijst steeds in twee even grote lijsten kan worden opgedeeld.

Leg uit waarom er bij het MergeSort-algoritme nauwelijks verschil is tussen het bestcase- en worstcasescenario.

Bekijk de volgende lijst met elementen. Kun je deze lijst het snelst sorteren met BubbleSort of met MergeSort?

1 2 5 4 6 5 9 8

1. BubbleSort
2. MergeSort

(Maar) waarom is BubbleSort sneller dan MergeSort om onderstaande lijst met elementen te sorteren?

1 2 5 4 6 5 9 8