Quicksort
Kiest één waarde, de spil, en zet kleinere waarden links ervan en grotere rechts. Daarna doet het hetzelfde met elke kant.
- beste geval Ω(n log n)
- gemiddeld Θ(n log n)
- slechtste geval O(n²)
- geheugen O(log n)
- niet 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
- spil
- 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 omgekeerde lijst. De spil is steeds de kleinste of grootste resterende waarde: één kant blijft leeg en de kosten lopen op naar n².
Hoe het werkt
Hier is de spil de laatste waarde van het bereik. Van links naar rechts wordt elke waarde die niet groter is dan de spil naar de linkerkant verwisseld. Daarna komt de spil tussen de twee kanten, waar hij voorgoed blijft. Elke kant wordt dan op dezelfde manier gesorteerd.
Wanneer het een goede keuze is
In de praktijk een van de snelste manieren om te sorteren, en het heeft bijna geen extra geheugen nodig. Maar kiest het steeds een slechte spil, bijvoorbeeld bij een lijst die al gesorteerd is, dan wordt het traag. Echte versies kiezen de spil zorgvuldiger.