Mergesort

MergeSort
1 / 21
volgende
Slide 1: Tekstslide
InformaticaMiddelbare schoolhavo, vwoLeerjaar 4-6

In deze les zitten 21 slides, met interactieve quizzen en tekstslides.

time-iconLesduur is: 50 min

Onderdelen in deze les

MergeSort

Slide 1 - Tekstslide

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

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 vraag

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

Slide 4 - Quizvraag

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

Slide 5 - Open vraag

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?”
timer
3:00

Slide 6 - Tekstslide

Zou dit werken?

Slide 7 - Tekstslide

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

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."
timer
3:00

Slide 9 - Tekstslide

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

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

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

Divide-and-conquermethode

Slide 13 - Tekstslide

Getallen sorteren met MergeSort
4         3         5         9         3        1         6

Slide 14 - Tekstslide

Getallen sorteren met MergeSort

Slide 15 - Tekstslide

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

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

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

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

Slide 19 - Open vraag

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

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

Slide 21 - Open vraag