Les 2 - Bubblesort

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

Cette leçon contient 27 diapositives, avec quiz interactifs, diapositives de texte et 1 vidéo.

time-iconLa durée de la leçon est: 50 min

Éléments de cette leçon

Bubble sort
BubbleSort

Slide 1 - Diapositive

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

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

Slide 3 - Question ouverte

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

Slide 4 - Question ouverte

Wat maakt een goed algoritme?
timer
1:00

Slide 5 - Question ouverte

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

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

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

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

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

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

Slide 11 - Question ouverte

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

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

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

....., 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 - Diapositive

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

  • BubbleSort
  • MergeSort
  • QuickSort

Slide 16 - Diapositive

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

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

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

Slide 20 - Vidéo

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

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

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