Les 4 - Mergesort

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

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

time-iconLesduur is: 50 min

Onderdelen in deze les

MergeSort

Slide 1 - Tekstslide

Deze slide heeft geen instructies

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

Deze slide heeft geen instructies

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

Slide 3 - Quizvraag

Deze slide heeft geen instructies

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

Slide 4 - Open vraag

Deze slide heeft geen instructies

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

Deze slide heeft geen instructies

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

Deze slide heeft geen instructies

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

Slide 7 - Tekstslide

Deze slide heeft geen instructies

Wat bedoelen we met divide-and-conquermethode?

Slide 8 - Open vraag

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

Slide 9 - Tekstslide

Deze slide heeft geen instructies

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

Slide 10 - Tekstslide

Deze slide heeft geen instructies

Slide 11 - Tekstslide

Deze slide heeft geen instructies

Slide 12 - Tekstslide

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

Slide 13 - Tekstslide

Deze slide heeft geen instructies

Slide 14 - Tekstslide

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

Slide 15 - Tekstslide

Deze slide heeft geen instructies

Slide 16 - Tekstslide

Deze slide heeft geen instructies

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

Slide 17 - Tekstslide

Merge sort en Quick sort met bijziende robots: https://youtu.be/es2T6KY45cA
Getallen sorteren met MergeSort
4         3         5         9         3        1         6

Slide 18 - Tekstslide

Deze slide heeft geen instructies

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

Slide 19 - Quizvraag

Deze slide heeft geen instructies

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

Deze slide heeft geen instructies

Getallen sorteren met MergeSort

Slide 21 - Tekstslide

Deze slide heeft geen instructies

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

Deze slide heeft geen instructies

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

Deze slide heeft geen instructies

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

Deze slide heeft geen instructies

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

Slide 25 - Open vraag

Deze slide heeft geen instructies

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

Deze slide heeft geen instructies

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

Slide 27 - Open vraag

Deze slide heeft geen instructies

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

Deze slide heeft geen instructies

Zou dit werken?

Slide 29 - Tekstslide

Deze slide heeft geen instructies

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

Deze slide heeft geen instructies

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

Deze slide heeft geen instructies

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

Deze slide heeft geen instructies