Les 2 - Bubblesort

Bubble sort
BubbleSort
1 / 27
next
Slide 1: Slide
InformaticaMiddelbare schoolhavo, vwoLeerjaar 4-6

This lesson contains 27 slides, with interactive quizzes, text slides and 1 video.

time-iconLesson duration is: 50 min

Items in this lesson

Bubble sort
BubbleSort

Slide 1 - Slide

Leerdoel
Aan het eind van deze les ken je het principe van het BubbleSort algoritme en kan je elementen uit een lijst sorteren aan de hand van het bubblesort algoritme.

Slide 2 - Slide

Wat is de definitie van een algoritme?
timer
1:00

Slide 3 - Open question

Waarom is het handig om een algoritme weer te geven in een schema?
timer
1:00

Slide 4 - Open question

Wat maakt een goed algoritme?
timer
1:00

Slide 5 - Open question

De efficiëntie van een algoritme kan bepaald worden aan de hand van drie scenario's.
Welke drie scenario's zijn dat?
timer
1:00

Slide 6 - Open question

Oefening 1
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?
timer
5:00

Slide 7 - Slide

Oefening 2
We gaan dezelfde opdracht nog een keer uitvoeren. De instructie is nu echter als volgt:
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?
timer
5:00

Slide 8 - Slide

Vaker voorkomende problemen
Sommige problemen komen vaker 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

Slide 9 - Slide

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.

Slide 10 - Slide

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

Slide 11 - Open question

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

Slide 12 - Slide

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.

Slide 13 - Slide

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

Slide 14 - Slide

....., 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 beter gebruik maken van een standaard sortteeralgoritme.

Slide 15 - Slide

Standaard sorteeralgoritme
De komende lessen zullen gaan we drie standaard sorteeralgoritmen behandelen:

  • BubbleSort
  • MergeSort
  • QuickSort

Slide 16 - Slide

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.

Slide 17 - Slide

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.

Slide 18 - Slide

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

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

Slide 19 - Slide

Slide 20 - Video

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

Slide 21 - Open question

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

Slide 22 - Open question

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

Slide 23 - Quiz

Het BubbleSort algoritme doorloopt altijd minstens twee keer de hele lijst.
A
Juist
B
Onjuist

Slide 24 - Quiz

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

Slide 25 - Quiz

Een al gesorteerde lijst is een bestcasescenario voor BubbleSort.
A
Juist
B
Onjuist

Slide 26 - Quiz

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

Slide 27 - Open question