Selectiesortering
Zoekt de kleinste overgebleven waarde en zet die met één verwisseling op de volgende plek. Het verwisselt heel weinig, maar vergelijkt altijd even vaak.
- beste geval Ω(n²)
- gemiddeld Θ(n²)
- slechtste geval O(n²)
- geheugen O(1)
- 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
- kleinste tot nu toe
- 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. Het aantal vergelijkingen is precies hetzelfde als bij elke andere lijst.
Hoe het werkt
Zoek in het ongesorteerde deel de kleinste waarde. Verwissel die met de eerste ongesorteerde waarde, zodat er weer een waarde op zijn definitieve plek staat. Het bekijkt altijd elke overgebleven waarde, ook als de lijst al gesorteerd is.
Wanneer het een goede keuze is
Handig als data verplaatsen duur is maar lezen goedkoop, want het verwisselt hooguit één keer per plek. In de meeste andere gevallen is invoegsortering de betere eenvoudige keuze.