Les 3 - Mergesort

MergeSort
1 / 23
next
Slide 1: Slide
InformaticaMiddelbare schoolhavo, vwoLeerjaar 4-6

This lesson contains 23 slides, with interactive quizzes and text slides.

time-iconLesson duration is: 50 min

Items in this lesson

MergeSort

Slide 1 - Slide

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.

Slide 2 - Slide

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
timer
2:00

Slide 3 - Open question

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

Slide 4 - Quiz

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

Slide 5 - Open question

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?”

Slide 6 - Slide

Zou dit werken?

Slide 7 - Slide

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 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

Slide 8 - Slide

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."

Slide 9 - Slide

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."

Slide 10 - Open question

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.

Slide 11 - Slide

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.

Slide 12 - Slide

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,

Slide 13 - Slide

Divide-and-conquermethode

Slide 14 - Slide

Getallen sorteren met MergeSort
4         3         5         9         3        1         6

Slide 15 - Slide

Getallen sorteren met MergeSort

Slide 16 - Slide

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

5 9 5 2 1 9 5

Slide 17 - Slide

uitwerking
5-9-5-2-1-9-5
5-9-5-2
5-9
5-2
1-9-5
1-9
5
5-9
2-5
1-9
5
Verdeelfase
oplossen
samenvoegen
2-5-5-9
1-5-9
1-2-5-5-5-9

Slide 18 - Slide

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

Slide 19 - Slide

Wat bepaalt in de verdeelfase van MergeSort het aantal stappen dat je moet nemen?
A
De mate waarin de lijst al gesorteerd is.
B
Het aantal elementen van de lijst.
C
De hoeveelheid dezelfde elementen in de lijst.
D
In hoeverre de lijst steeds in twee even grote lijsten kan worden opgedeeld.

Slide 20 - Quiz

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

Slide 21 - Open question

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
A
BubbleSort
B
MergeSort

Slide 22 - Quiz

(Maar) waarom is BubbleSort sneller dan MergeSort om onderstaande lijst met elementen te sorteren?
1 2 5 4 6 5 9 8

Slide 23 - Open question