Inleiding

Je klastitularis wilt opnieuw de 20 leerlingen van je klas sorteren van klein naar groot. Deze keer kiest hij/zij voor een andere strategie.

Alle leerlingen staan in één rij, willekeurig door elkaar. De klastitularis gaat als volgt te werk:

0) De klastitularis begint vooraan in de rij en vergelijkt de twee eerste leerlingen die naast elkaar staan (index 0 en 1). Als de linker leerling groter is dan de rechter, wisselen ze van plaats. Daarna doen we verder met de volgende leerlingen (index 1 en 2). Door dit herhaaldelijk uit te voeren, “drijft” de grootste leerling helemaal naar “boven” in de rij. Wanneer alle elementen overlopen zijn, bestaat de groep leerlingen uit een deelgroep van 1 leerling (achteraan) die zeker op de juiste plaats staat, en een ongeordende deelgroep van 19 leerlingen.

1) De klastitularis herhaalt hetzelfde proces, maar hoeft de laatste leerling niet meer te bekijken - deze staat immers al op de juiste plaats. Opnieuw “drijft” de grootste leerling van het ongeordende deel naar “boven”. Je hebt nu een deelgroep van 2 leerlingen achteraan die geordend zijn, en een ongeordende deelgroep van 18 leerlingen.

2) De klastitularis herhaalt hetzelfde proces, maar hoeft de twee laatste leerlingen niet meer te bekijken - deze staan immers al op de juiste plaats. Opnieuw “drijft” de grootste leerling van het ongeordende deel naar “boven”. Je hebt nu een deelgroep van 3 leerlingen achteraan die geordend zijn, en een ongeordende deelgroep van 17 leerlingen.

3) De klastitularis herhaalt dit proces opnieuw, telkens op een kleiner deel van de rij. Het algoritme eindigt wanneer de volledige rij geordend is.

Dit algoritme wordt Bubble sort genoemd, omdat grotere elementen als het ware naar boven (achteraan) drijven (“bubbelen”) in de lijst.

Concreet stappenplan voor lijsten

In het begin is de lijst niet gesorteerd.

0) Overloop de lijst en vergelijk telkens twee opeenvolgende elementen. Verwissel ze indien nodig. Op het einde van deze stap staat het grootste element op het einde van de lijst. Met andere woorden: de deellijst lijst[-1:] is nu gesorteerd.

1) Overloop opnieuw de lijst, vergelijk telkens twee opeenvolgende elementen en verwissel indien nodig. Stop één element vroeger. De deellijst lijst[-2:] is nu gesorteerd.

2) Overloop opnieuw de lijst, vergelijk telkens twee opeenvolgende elementen en verwissel indien nodig. Stop twee elementen vroeger. De deellijst lijst[-3:] is nu gesorteerd.

3) Herhaal dit proces, telkens op een korter deel van de lijst. Blijf doorgaan tot de volledige lijst gesorteerd is.

Opgave

0) Pas bovenstaand stappenplan toe op de lijst [9, -5, 8, -3, -10, 4, 5]. Noteer de volledige lijst na elke doorloop (na stap 0, stap 1, …) tot de lijst volledig gesorteerd is.

1) Schrijf een functie verwissel_buren(lijst, i). lijst is een lijst met getallen. i is een index. De functie vergelijkt de elementen op index i en i+1. Als het element op index i groter is dan dat op i+1, worden ze verwisseld. Anders blijft de lijst ongewijzigd. De functie geeft de (al dan niet aangepaste) lijst terug.

2) Schrijf een functie doorloop(lijst, einde). lijst is een lijst met getallen. einde is een index. De functie doorloopt de lijst van index 0 tot en met einde - 1, en past daarbij verwissel_buren toe wanneer dat nodig is. De functie geeft de aangepaste lijst terug na één volledige doorloop.

3) Schrijf een functie bubble_sort(lijst). lijst is een lijst met getallen. De functie past herhaaldelijk de bovenstaande stappen toe, en verkleint telkens het deel van de lijst dat moet bekeken worden. De functie stopt wanneer de volledige lijst gesorteerd is, en geeft dan de gesorteerde lijst terug.

4) Stel dat je een lijst van 100 elementen wilt sorteren. Hoeveel keer moet je in totaal twee opeenvolgende elementen met elkaar vergelijken? Hoeveel stappen heb je nodig voor een lijst van 200 elementen? En voor een lijst van 400 elementen? Met de leerstof wiskunde van het vijfde moet je een patroon kunnen zien ontstaan.

5) Hoe zou de uitvoertijd van dit algoritme evolueren wanneer n, het aantal elementen van de lijst, “groot” wordt? Stel dat bubble_sort() 1 seconde nodig heeft om een lijst van 10000 elementen te sorteren. Hoe lang zou het dan bij benadering duren om een lijst van 40000 elementen te sorteren?

Voorbeeld 1

Invoer:

> verwissel_buren([5, 3, 7], 0)

Uitvoer:

[3, 5, 7]

Voorbeeld 2

Invoer:

> doorloop([9, -5, 8, -3], 3)

Uitvoer:

[-5, 8, -3, 9]

Voorbeeld 3

Invoer:

> bubble_sort([9, -5, 8, -3, -10, 4, 5])

Uitvoer:

[-10, -5, -3, 4, 5, 8, 9]