Invoegsortering
Bouwt links een gesorteerd deel op, één waarde tegelijk. Elke nieuwe waarde wordt eruit gehaald en naar links verplaatst tot ze een kleinere waarde tegenkomt.
- 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
- in de hand
- gesorteerd deel
- 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. Er schuift bijna niets, dus het is in heel weinig stappen klaar.
Hoe het werkt
Het linkerdeel is altijd gesorteerd. Haal de volgende waarde eruit en schuif elke grotere waarde in het gesorteerde deel één plek naar rechts. Zet de waarde dan in het gat. Zo sorteren veel mensen de speelkaarten in hun hand.
Wanneer het een goede keuze is
Een goede keuze voor korte lijsten en voor lijsten die bijna gesorteerd zijn. Daar is het heel snel. Echte sorteerbibliotheken gebruiken het binnen snellere methoden voor de kleine stukjes van een lijst.