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.

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

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,

Een grappige video over divide-and-conquer algoritmes hier:

Vind de vieze sokken van Santa vóór 12 uur in een stapel van 1064 doosjes in maar 10 stappen

Wat bedoelen we met divide-and-conquermethode?

Het probleem wordt steeds verder verkleind, totdat het deelprobleem klein genoeg is om het op te lossen. Bij Quicksort en Mergesort is dit goed te zien.

Divide-and-conquermethode

Merge sort: Een efficient sorteeralgoritme, dat gebruik maakt van de zg. divide- and- conquer methode

De lijst is helemaal opgedeeld.

Nu de 1e items vergelijken. Het kleinste item in een nieuwe, tijdelijke lijst plaatsen en weghalen uit de oude lijst.

Zodra 1 lijst leeg is, de rest van de andere lijst erachteraan plakken

Hier krijg je 3 4 5 en dan plak je 6 en 8 erachteraan. De andere lijst is dan nl. leeg

Merge sort met Quick sort vergelijken, gebeurt hier met bijziende robots

Merge sort en Quick sort met bijziende robots: https://youtu.be/es2T6KY45cA

Getallen sorteren met MergeSort

4         3         5         9         3        1         6

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

2 1 4 5 6 5 9 8

1. BubbleSort
2. MergeSort

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.

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

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.