Les 3 - Bubblesort

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

Bubble sort

BubbleSort

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.

Wat is de definitie van een algoritme?

Waarom is het handig om een algoritme weer te geven in een schema?

Wat maakt een goed algoritme?

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

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?

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?

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

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.

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.

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

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

Standaard sorteeralgoritme

De komende lessen zullen gaan we drie standaard sorteeralgoritmen behandelen:

• BubbleSort
• MergeSort
• QuickSort

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: 6-9-7-3 6-7-9-3 6-7-3-9
• Ronde 2: 6-3-7-9
• Ronde 3: 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

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

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

1. Juist
2. Onjuist

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

1. Juist
2. Onjuist

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

1. Juist
2. Onjuist

Een al gesorteerde lijst is een bestcasescenario voor BubbleSort.

1. Juist
2. Onjuist

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