Bubblesort
Bubblesort, soms ook exchange sort of sinking sort genoemd, is een van de meest eenvoudige sorteeralgoritmes. Dit algoritme kun je gebruiken om een lijst van getallen te sorteren, maar het is niet heel erg efficiënt. Het werkt als volgt:
- Start bij het eerste element in de lijst. Zolang als dit element groter is dan het element dat erna komt, wissel je deze elementen om. Blijf dit doen totdat je aan het einde van de lijst bent. Het laatste element in de lijst is nu gegarandeerd het grootste element.
- Start opnieuw vanaf het eerste element in de lijst en blijf elementen omwisselen totdat je aan de voorlaatste positie in de lijst bent (de laatste hoef je niet meer te checken). Nu staat het tweede grootste element op de tweede laatste positie.
- Start opnieuw vanaf het eerste element en blijf omwisselen totdat je aan het derde laatste element bent.
- Ga zo door totdat je de ganse lijst gehad hebt.
We zien de grotere elementen als het ware als luchtbellen naar boven drijven. Aan deze metafoor ontleent het algoritme zijn naam. Onderstaande animatie toont Bubblesort in actie op een lijst van willekeurige getallen:
Stel dat we Bubblesort toepassen op de volgende lijst:
[5, 4, 3, 2, 1]
Na de eerste iteratie hebben we
[4, 3, 2, 1] + [5]
Het grootste element staat dus achteraan. Na de tweede iteratie:
[3, 2, 1] + [4, 5]
Na de derde iteratie:
[2, 1] + [3, 4, 5]
Na de vierde iteratie:
[1] + [2, 3, 4, 5]
Na de vijfde iteratie:
[1, 2, 3, 4, 5]
Nu zijn we klaar.
Opgave
Implementeer het Bubblesort-algoritme om een lijst van getallen te sorteren.
Voorbeeld
Invoer:
14
70
35
27
37
93
7
73
68
64
Uitvoer:
7
14
27
35
37
64
68
70
73
93