Bubblesort is een eenvoudig sorteeralgoritme dat herhaaldelijk door de lijst gaat, paren van aangrenzende elementen vergelijkt en ze verwisselt als ze in de verkeerde volgorde staan. Dit proces wordt herhaald totdat de lijst volledig gesorteerd is. De naam “Bubblesort” komt van het idee dat de grotere (of kleinere, afhankelijk van de sorteervolgorde) elementen “omhoog bubbelen” naar hun juiste positie, net als belletjes in een glas cola.

Hier is een basisstappenplan voor Bubblesort:

1. Begin aan het begin van de lijst.
2. Ga door de lijst en vergelijk aangrenzende elementen.
3. Als het huidige element groter (of kleiner) is dan het volgende element, wissel ze van plaats.
4. Ga door tot het einde van de lijst is bereikt.
5. Herhaal dit proces voor elke element in de lijst totdat er geen wisselingen meer plaatsvinden tijdens een doorloop.

Hoewel bubblesort eenvoudig te begrijpen en te implementeren is, heeft het een inefficiënte tijdscomplexiteit van O(n^2) in het slechtste en gemiddelde geval, wat betekent dat het langzaam kan zijn voor grote lijsten. Het is echter handig voor kleine lijsten of als een educatief hulpmiddel vanwege zijn eenvoud.

Schrijf een functie bubblesort met een lijst van getallen als parameter die een gesorteerde lijst als returnwaarde heeft.

>>> bubblesort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]
>>> bubblesort([73, 41, 74, 72, 8, 10, 57, 84, 68, 21])
[8, 10, 21, 41, 57, 68, 72, 73, 74, 84]