Backup -> Les 3 en 4: Standaardalgoritmen Bubblesort, Mergesort en Quicksort

BubbleSort

Standaard algoritmen

1 / 82
volgende
Slide 1: Slide
newEditorInformaticaMiddelbare schoolhavo, vwoLeerjaar 4-6

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

time-iconLesduur is: 50 min
Dit is niet oké

Onderdelen in deze les

BubbleSort

Standaard algoritmen

Leerdoel

Aan het eind van deze les kun je wat meer vertellen over standaard algoritmen en over de principes van het BubbleSort algoritme. Ook kan je elementen uit een lijst sorteren aan de hand van dit algoritme.

Iemand neemt een getal tussen de 1 en de 60 in gedachten. Jij moet raden welk getal dat is. Je gebruikt daarbij het in de vorige les behandelde algoritme. Welk getal hoort bij het bestcasescenario?

A

29

B

30

C

60

D

61

Dezelfde situatie. In hoeveel stappen raad je het getal in een worstcasescenario?

A

6

B

15

C

30

D

60

In hoeveel stappen raad je het getal in een worstcasescenario?

Het worstcasescenario is het maximum aantal stappen. 

Halveren geeft 30 – 15 – 8 – 4 – 2 – 1, dus in 6 stappen.

Nog een zoekalgoritme in de praktijk...

 Een ander voorbeeld van een zoekalgoritme is voor het zoeken van een woord in een woordenboek. Je bent op zoek naar de betekenis van een woord. Je gebruikt hierbij de dikke Van Dale, die 1000 bladzijdes telt.



Beschrijf een snel algoritme om de juiste bladzijde te vinden waarop het woord staat dat je zoekt.

Wat is ESSENTIEEL om een woord snel op te kunnen zoeken in een woordenboek?

A

Dat de bladzijden in het boek genummerd zijn

B

Dat de zoekwoorden alfabetisch gesorteerd zijn

C


D


Sorteren is dus belangrijk en een voorbeeld van een vaker voorkomend probleem

Situaties waarin gesorteerd moet worden komen vaak voor. Bijvoorbeeld:

  • Het sorteren van een stapel speelkaarten

  • het sorteren van een tabel in Excel van klein naar groot

  • het sorteren van een stapel toetsen op alfabet

Vaker voorkomende problemen

Voor veel van deze vaker voorkomende problemen zijn standaardalgoritmen gemaakt. Deze standaardalgoritmen kunnen op verschillende gebieden worden gebruikt. De werking zal echter overal redelijk gelijk zijn.

Algoritmen worden niet alleen gebruikt om te sorteren. Noem nog een toepassing waar een standaardalgoritme van pas kan komen.

1

minute

00

second

Toepassing standaardalgoritmen

Naast sorteren zijn er nog veel meer toepassingen waar standaardalgoritmen van pas komen. Bijvoorbeeld:


  • Het berekenen van een route tussen twee adressen in een routeplanner

  • de automatische tekstcorrectie op je telefoon

  • de algemene werking van een zoekmachine zoals Google

Standaard sorteeralgoritmen

Een sorteeralgoritme is een algoritme dat een lijst met elementen in een bepaalde volgorde kan sorteren. 


Een lijst kan een stapel met kaarten zijn. Maar ook een aantal verschillende getallen of stukken tekst. Een element is een losse kaart in de stapel, een getal of stuk tekst in de lijst.

Oefening: denken als een computer

Vorm een groepje van 3 leerlingen. Je krijgt met je groepje een setje getallen (1 t/m 9). Leg deze naast elkaar met de cijfers naar beneden. Hoe ga je ervoor zorgen dat je de cijfers op volgorde van 1 naar 9 kan krijgen? Hoe krijg je ze dus gesorteerd?

Oefening: denken als een computer

Een computer kan slechts 2 getallen met elkaar vergelijken. De computer heeft geen kennis van de andere getallen in de reeks.

Je gaat als volgt te werk: 

  • Een persoon mag twee getallen tegelijkertijd laten zien aan een tweede persoon.

  • Deze tweede persoon mag alleen aangeven welk getal groter is. 

  • De derde persoon telt hoe vaak de de stappen worden doorlopen voordat de hele rij is gesorteerd. 


Hoe pak je dit aan?

3

minute

00

second

Uitwerking: denken als een computer

Persoon 1: Kiest twee getallen en draait ze om.

Persoon 2: Vergelijkt de getallen en geeft aan welk getal groter is.

Persoon 1: Plaatst de getallen opnieuw met het grotere getal naar voren.


Herhaal het proces voor alle getallen in de lijst, vergelijk steeds het grotere getal met het volgende. Na elke ronde, negeer het laatste getal (dat op de juiste plek staat) en begin opnieuw.


Persoon 3: Telt het aantal vergelijkingen dat wordt gemaakt totdat de lijst volledig gesorteerd is. Dit geeft inzicht geeft in de efficiëntie van het sorteerproces.




Dit is makkelijk.....

Een lijst met weinig elementen kan je in één oogopslag sorteren. Kijk bijvoorbeeld eens naar onderstaande lijst met elementen. Zet deze op volgorde van groot naar klein.


8 9 1 5


Je ziet direct dat de laatste twee getallen naar voren moeten

Verwarrend?
Laten we de situatie vereenvoudigen met cijfers

....., maar dit niet meer

Als een lijst groter wordt dan is het nauwelijks nog te doen voor een mens.


21 55 23 66 22 13 98 42 10 39 84 17 10 62 81 29 47 16 39 64 3 83 27 59 12 18 45 64 29


Om bovenstaande reeks te sorteren kan je dus beter gebruik maken van een standaard sorteeralgoritme.

Standaard sorteeralgoritme

We zullen drie standaard sorteeralgoritmen behandelen om dergelijke lijsten te sorteren:


  • BubbleSort

  • MergeSort

  • QuickSort

BubbleSort


BubbleSort

BubbleSort is een eenvoudig sorteeralgoritme. Het is één van de meest efficiënte algoritmen voor lijsten met weinig elementen die al bijna volledig gesorteerd zijn. Maar voor het sorteren van lijsten met veel elementen is het minder geschikt.

Werking BubbleSort

  1. Doorloop de te sorteren lijst vanaf de linkerkant.

  2. Vergelijk ieder element met het volgende element in de lijst. 

  3. Verwissel de elementen als het huidige element groter is dan het volgende element.
     

  4. Aan het einde van de lijst: begin opnieuw en herhaal stap 1 t/m 4 totdat alles gesorteerd is.

Voorbeeld BubbleSort

Stel, je hebt een lijst met de volgende elementen: 9-6-7-3


  • Ronde 1: 9-6-7-3   6-9-7-3   6-7-9-3   6-7-3-9

  • Ronde 2: 6-7-3-9   6-3-7-9

  • Ronde 3: 6-3-7-9   3-6-7-9

Sorteer de volgende lijst met elementen in de juiste volgorde van klein naar groot met behulp van BubbleSort. Gebruik hiervoor het stappenplan uit het voorbeeld.

2-6-1-8-3

2

minute

00

second

Uitwerking 2-6-1-8-3


Sorteer de volgende lijst met elementen in de juiste volgorde van klein naar groot met behulp van BubbleSort. Gebruik hiervoor het stappenplan uit het voorbeeld.

1-6-3-4-5

2

minute

00

second

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

A

Juist

B

Onjuist

C


D


Het BubbleSort algoritme doorloopt altijd minstens twee keer de hele lijst.

A

Juist

B

Onjuist

C


D


Een lijst waarin maar één verwisseling hoeft te worden gedaan is een bestcasescenario voor BubbleSort.

A

Juist

B

Onjuist

C


D


Een al gesorteerde lijst is een bestcasescenario voor BubbleSort.

A

Juist

B

Onjuist

C


D


Geef een lijst met de 5 elementen 1, 2, 3, 4 en 5 waarin sprake is van een worstcasescenario bij BubbleSort

1

minute

00

second

Leerdoel gehaald?

Aan het eind van deze les kun je wat meer vertellen over standaard algoritmen en over de principes van het BubbleSort algoritme. Ook kan je elementen uit een lijst sorteren aan de hand van dit algoritme.

Doornemen

LessonUp

Les 2 - Standaard algoritmen - BubbleSort

Fundament 

B: Grondslagen -> Algoritmen (B1) -> 2. Standaard algoritmen 2.1 - 2.3

MergeSort

QuickSort

Standaard algoritmen

Leerdoel

Aan het eind van deze les kun je wat meer vertellen over de principes van het het MergeSort algoritme en het het QuickSort algoritme. Ook kan je elementen uit een lijst sorteren aan de hand van deze algoritmes en leer je een manier om snel te tellen.

Het bubble sort-algoritme weet dat het klaar is als er geen verwisselingen meer nodig zijn.

A

Juist

B

Onjuist

C


D


Selecteer een worstcasescenario bij BubbleSort.

A

Een lijst met 1250 elementen.

B

De lijst 7-3-6-2-2-5-8.

C

Een lijst met 15 elementen die gesorteerd is van groot naar klein.

D

Een lijst met 15 elementen die gesorteerd is van klein naar groot.

Selecteer een worstcasescenario bij BubbleSort.

Lijsten met veel elementen en lijsten die van groot naar klein gesorteerd zijn, nemen erg veel tijd in beslag bij het bubble sort-algoritme.

Divide-and-conquer

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 (verdeel en heers) 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


Divide-and-conquermethode

Zoals we zullen zien gebruiken
MergeSort en QuickSort

beide de
Divide-and-conquermethode

MergeSort


MergeSort

MergeSort is een efficiënt sorteeralgoritme, dat gebruik maakt van de
zg. divide-and-conquer methode (het verdeel en heers-principe). MergeSort is een recursief algoritme, wat betekent dat het algoritme zichzelf herhaalt.

Werking MergeSort

  1. Verdeel de lijst in twee deellijsten.

  2. Herhaal stap 1 totdat alle deellijsten nog maar één element hebben.

  3. Voeg alle deellijsten een voor een samen tot een gesorteerde nieuwe lijst. Bij het samenvoegen wordt het eerste element vergeleken met de andere elementen. Zo wordt de juiste volgorde bepaald.

Voorbeelden MergeSort

  9 2 7 3                                                     4 1 7 5 3 2 6

Oefenen!

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


 1 7 8 7 2

Uitwerking: sorteren 1 7 8 7 2 


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?

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.

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

Het aantal stappen dat je moet nemen wordt bepaald door het aantal getallen dat je gaat sorteren. Omdat je in de verdeelfase de lijst opdeelt in deellijsten tot er maar één element overblijft, maakt het niet uit welke getallen er staan, maar alleen hoeveel getallen.

Zoals elk algoritme, kent ook MergeSort best- en worstcasescenario's. Is er bij MergeSort een groot verschil tussen het best- en worstcasescenario?

A

Ja, want een kortere lijst is altijd gunstiger dan een langere lijst.

B

Nee, want deze methode kent geen best- of worstcasescenario.

C

Nee, want in elk scenario is het aantal stappen hetzelfde.

D

Ja, want het aantal deellijsten bepaalt het gemak waarmee de lijst gesorteerd kan worden.

Is er bij MergeSort een groot verschil tussen het best- en worstcase?

Zoals je bij de voortgaande vraag gezien hebt, blijkt dat de verdeelfase voor alle scenario's gelijk is. Ook in de verzamelfase is er geen verschil: je voegt de lijsten samen door steeds de eerste elementen van de deellijsten met elkaar te vergelijken. Dat vergelijken moet in elk scenario gebeuren. Afhankelijk van de grootte van die getallen moet je dan het getal uit de linker- of de rechter deellijst kiezen. Alleen daar is er een verschil tussen best- 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

A

BubbleSort

B

MergeSort

C


D


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

1 2 5 4 6 5 9 8

1

minute

00

second

Kun je deze lijst het snelst sorteren met BubbleSort of met MergeSort?

Je voert de volgende wisselingen uit:
1 2 4 5 6 5 9 8 - 1 2 4 5 5 6 9 8 -
1 2 4 5 5 6 8 9.




Met MergeSort ben je langer bezig: eerst moet je de lijst meermaals opsplitsen, waarna je de deellijsten gesorteerd samenvoegt. De lijst is al grotendeels gesorteerd, dus je zult veel deellijsten samenvoegen die eigenlijk al gesorteerd waren.

Je kunt dus beter BubbleSort gebruiken om deze lijst te sorteren.



Intermezzo: snel tellen

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

1

minute

30

second

Zou dit werken?

  1. Alle leerlingen gaan staan

  2. Alle leerlingen krijgen het getal 1

  3. Voor iedereen die nog staat: kijk je buur aan en spreek af:
    a) Eentje gaat zitten
    b) De ander telt jullie getallen bij elkaar op, en onthoudt dat nieuwe getal

  4. Herhaal dit tot er één leerling over is.


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


In hoeveel stappen kun je met deze methode 1024 leerlingen tellen?

A

1 keer

B

6 keer

C

10 keer

D

1024 keer

In hoeveel stappen kun je met deze methode 1024 leerlingen tellen?

Met elke stap kun je 2x zoveel leerlingen tellen, dus:


  • 1024 leerlingen kun je in 10 stappen tellen.

  • En het 2048 (het dubbele) in 11 stappen.

  • Heel Nederland? Met maar zo’n 24 stappen (2^24 = 16,78 miljoen mensen).


QuickSort


QuickSort

Het QuickSort algoritme maakt net zoals het MergeSort algoritme gebruik van de divide-and-conquermethode.


Door de werking van het QuickSort algoritme pakt onder andere de worstcasescenario van QuickSort minder slecht uit dan dat van MergeSort.

Werking QuickSort

  1. Kies een willekeurig element uit de lijst. Dit element wordt de pivot genoemd.

  2. Verplaats de elementen als volgt:

    a. Elementen met een waarde kleiner of gelijk aan de pivot komen links van de pivot.
    b. Elementen met een waarde groter dan de pivot komen rechts van de pivot.

  3. Voer stappen 1 en 2 uit op de deellijsten links en rechts van de pivot.

  4. Herhaal stap 3 totdat alles gesorteerd is.

Voorbeeld

Sorteer de volgende elementen. Kies als pivot steeds het meest linker element. Schrijf alle stappen uit!


5  3  8  2  7  1

Antwoord

Sorteer de volgende elementen. Kies als pivot steeds het meest linker element.


5  3  8  2  7  1



Oefenvraag 1

Sorteer de volgende elementen. Kies als pivot steeds het meest linker element. Schrijf alle stappen uit!


4 8 2 9 1 5

Antwoord oefenvraag 1

Sorteer de volgende elementen. Kies als pivot steeds het meest linker element. Schrijf alle stappen uit!


4 8 2 9 1 5

Oefenvraag 2

Sorteer de volgende elementen. Kies als pivot steeds het meest linker element. Schrijf alle stappen uit!


1  9  7  9  1  7

Antwoord oefenvraag 2

Sorteer de volgende elementen. Kies als pivot steeds het meest linker element. Schrijf alle stappen uit!


1  9  7  9  1  7

Keuze van de pivot

Tot nu toe hebben we steeds als pivot het meest linker element gekozen. De pivot mag echter willekeurig gekozen worden.


Het algoritme werkt dus ook als je bijvoorbeeld steeds het middelste element van de lijst kiest of het meest rechter element.

efficiëntie sorteeralgoritmes

De efficiëntie van een algoritme is van een aantal factoren afhankelijk. 


Bijvoorbeeld:


  • Is het een lijst met veel of weinig elementen?

  • Is de lijst al voor een deel gesorteerd?

  • Komen er (veel) dubbele elementen voor in de lijst?

efficiëntie sorteeralgoritmes

De efficiëntie van een algoritme is van een aantal factoren afhankelijk. 



Je wilt deze lijst met voornamen sorteren op alfabetische volgorde. Welk algoritme is hiervoor het meest efficiënt? Pieter, Sanne, Thomas, Pieter, Jesse, Pieter, Sanne, Thomas, Julia, Pieter, Jesse, Pieter, Jesse, Jesse, Pieter, Thomas, Jesse, Thomas, Pieter, Julia, Julia, Jesse, Thomas, Thomas, Julia

A

BubbleSort

B

MergeSort

C

QuickSort

D


Welk algoritme is het meest efficiënt voor het sorteren van een lijst met voornamen op alfabetische volgorde?

De lijst bevat veel dubbele namen en is grotendeels ongesorteerd. In dat scenario is merge sort het meest geschikt.

Je wilt deze lijst met getallen sorteren van klein naar groot. Welk algoritme is hiervoor het meest efficiënt? 10, 14, 16, 19, 20, 30, 25, 28, 60, 40, 50, 65, 70, 75, 90, 80, 85

A

BubbleSort

B

MergeSort

C

QuickSort

D


Welk algoritme is het meest efficiënt voor het sorteren van een lijst met getallen van klein naar groot?

De lijst bevat geen dubbele getallen en is grotendeels gesorteerd. In dat scenario is bubble sort het meest geschikt.

Leerdoel gehaald?

Aan het eind van deze les kun je wat meer vertellen over de principes van het het MergeSort algoritme en het het QuickSort algoritme. Ook kan je elementen uit een lijst sorteren aan de hand van deze algoritmes en leer je een manier om snel te tellen.

Doornemen

LessonUp

Les 3 - Standaard algoritmen - MergeSort en QuickSort

Fundament 

B: Grondslagen -> Algoritmen (B1) -> 2. Standaard algoritmen 2.4 - 2.6

Tijd over? Oefenen met pivot


Zie voor uitwerking Fundament 2.5 - Vraag 3


Sorteer de lijsten 7 6 5 4 3 2 1 en 2 3 5 7 6 4 1 twee keer met QuickSort. 


Kies de eerste keer steeds het meest linker element als pivot. 


Kies de tweede keer steeds het middelste element als pivot. Als er geen middelste is, kies dan het eerste element rechts van het midden als pivot.