Bubblesort
Loopt de lijst steeds opnieuw door en verwisselt buren die in de verkeerde volgorde staan. Na elke ronde staat de grootste overgebleven waarde achteraan.
- beste geval Ω(n)
- gemiddeld Θ(n²)
- slechtste geval O(n²)
- geheugen O(1)
- stabiel
- zonder extra geheugen
Wat betekent dit?
- Beste geval: hoe de tijd groeit met de lijstgrootte n als de invoer voor dit algoritme het makkelijkst is.
- Gemiddeld: de gewone groei van de tijd met n. Bij n² duren twee keer zoveel waarden ongeveer vier keer zo lang. n log n groeit veel trager.
- Slechtste geval: de groei bij de moeilijkste invoer. Handig als de snelheid nooit mag inzakken.
- Geheugen: hoeveel extra geheugen nodig is naast de lijst. 1 betekent een paar variabelen, n een kopie van de lijst.
- Stabiel: twee gelijke waarden houden hun oorspronkelijke volgorde. Belangrijk als je records op één veld sorteert.
- Zonder extra geheugen: sorteert in de lijst zelf, zonder tweede lijst.
- wordt vergeleken
- wordt verplaatst
- op definitieve plek
Druk op afspelen: de lijnen tonen hoe de kosten oplopen
Druk op afspelen of doorloop het algoritme stap voor stap.
Spatie: afspelen of pauzeren. Pijltjes links/rechts: stap. Home en End: springen.
Probeer dit: Kies een bijna gesorteerde lijst. Na één ronde zonder verwisselingen stopt het algoritme vroeg.
Hoe het werkt
Het vergelijkt steeds twee buren en verwisselt ze als de linker groter is. Zo komt in elke ronde de grootste waarde helemaal rechts terecht, als een opstijgende bel. Is er in een ronde niets verwisseld, dan is de lijst al gesorteerd.
Wanneer het een goede keuze is
Bijna nooit in echte programma's, want bij lange lijsten is het traag. Om te leren is het wel ideaal: het toont het basisidee van sorteren door vergelijken en verwisselen. Het is alleen snel als de lijst al gesorteerd is.