Bubblesort

Bubblesort is het eenvoudigste sorteeralgoritme om uit te leggen: vergelijk twee buren, verwissel ze als ze in de verkeerde volgorde staan, en herhaal. Het is traag op lange lijsten, maar elke stap is makkelijk te volgen. Daarom is het het klassieke eerste algoritme om naar te kijken.

Staven van verschillende hoogte die gesorteerd worden, met twee buren gemarkeerd voor een verwisseling en de hoogste staven al op hun plek aan het eind
Staven van verschillende hoogte die gesorteerd worden, met twee buren gemarkeerd voor een verwisseling en de hoogste staven al op hun plek aan het eind

Het idee

Loop van links naar rechts door de lijst en bekijk elk paar buren. Is de linker waarde groter dan de rechter, verwissel ze dan. Als je het eind bereikt, is de grootste waarde helemaal naar de laatste plek meegenomen, zoals een bel naar het oppervlak stijgt. Zo'n doorloop heet een ronde. Herhaal de rondes tot de lijst gesorteerd is.

Een voorbeeld

Neem 5, 1, 4, 2, 8. De eerste ronde vergelijkt 5 en 1 en verwisselt ze, dan 5 en 4 (verwisselen), 5 en 2 (verwisselen) en 5 en 8 (niet verwisselen): 1, 4, 2, 5, 8. De 8 staat nu op zijn definitieve plek. De tweede ronde vergelijkt 1 en 4 (niet verwisselen), 4 en 2 (verwisselen) en 4 en 5 (niet verwisselen): 1, 2, 4, 5, 8. De derde ronde verwisselt helemaal niets, dus de lijst is gesorteerd: 9 vergelijkingen en 4 verwisselingen.

Waarom elke ronde één waarde meer op zijn plek zet

Tijdens een ronde wordt de grootste waarde tot nu toe altijd meegenomen: zodra de ronde hem bereikt, schuift elke vergelijking hem één plek verder naar rechts. De eerste ronde zet dus de grootste waarde achteraan, de tweede ronde de op één na grootste vlak daarvoor, enzovoort. Na ronde k liggen de laatste k plekken vast en kan de volgende ronde één plek eerder stoppen. Daarom worden de rondes korter.

Verwisselingen zijn gelijk aan inversies

Een inversie is een paar waarden in de verkeerde volgorde: een grotere waarde ergens vóór een kleinere. Twee buren verwisselen die verkeerd staan, haalt precies één inversie weg en maakt er geen nieuwe. Bubblesort doet dus precies zoveel verwisselingen als de beginlijst inversies heeft, in welke volgorde de vergelijkingen ook komen. Een gesorteerde lijst heeft er geen; een omgekeerde lijst van n waarden heeft er n(n − 1)/2, het maximum.

De vroege stop en de kosten

Als een hele ronde niets verwisselt, staan alle buren op volgorde en is de lijst gesorteerd. Door daarop te controleren, sorteert bubblesort een gesorteerde lijst in één ronde van n − 1 vergelijkingen. In het slechtste geval zijn nog steeds n − 1 rondes en n(n − 1)/2 vergelijkingen nodig, en gemiddeld is het aantal verwisselingen n(n − 1)/4. Beide groeien met n², dus een twee keer zo lange lijst kost ongeveer vier keer zoveel tijd.

Bubblesort is stabiel: gelijke waarden worden nooit verwisseld, dus ze houden hun volgorde. Het sorteert ter plekke, zonder extra geheugen. Insertion sort heeft dezelfde eigenschappen en heeft meestal minder stappen nodig, en merge sort en quicksort kosten tijd evenredig met n log n, wat op lange lijsten veel minder is.

Probeer het zelf

Open de app en druk op Afspelen, of druk op Stap om per vergelijking te gaan. De twee waarden die vergeleken worden zijn gemarkeerd, een verwisseling krijgt een eigen kleur, en waarden die al op hun plek staan worden groen. Probeer een omgekeerde lijst voor het slechtste geval, een bijna gesorteerde om de vroege stop na een paar rondes te zien ingrijpen, of typ de getallen uit het voorbeeld hierboven.

Veelgestelde vragen

Wat is de tijdcomplexiteit van bubblesort?

O(n²) in het slechtste en gemiddelde geval: tot n(n − 1)/2 vergelijkingen bij n waarden. Met de vroege stop kost een al gesorteerde lijst O(n), één ronde. Er is maar O(1) extra geheugen nodig.

Is bubblesort stabiel?

Ja. Het verwisselt twee buren alleen als de linker strikt groter is, dus gelijke waarden passeren elkaar nooit en houden hun oorspronkelijke volgorde.

Wat is het verschil tussen bubblesort en insertion sort?

Beide verwisselen buren en beide doen evenveel verwisselingen als er inversies zijn. Bubblesort maakt volledige rondes over het ongesorteerde deel; insertion sort schuift elke nieuwe waarde maar zo ver terug als nodig, dus doet het meestal minder vergelijkingen, vooral op bijna gesorteerde lijsten.

Wanneer is bubblesort een goede keuze?

Vooral in het onderwijs, en voor heel korte lijsten waar eenvoud belangrijker is dan snelheid. Voor alles wat groter is, is de ingebouwde sorteerfunctie van je programmeertaal veel sneller.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Probeer bubblesort