Insättningssortering
Bygger upp en sorterad del till vänster, ett värde i taget. Varje nytt värde lyfts ut och flyttas åt vänster tills det når ett mindre värde.
- bästa fall Ω(n)
- genomsnitt Θ(n²)
- värsta fall O(n²)
- minne O(1)
- stabil
- utan extra minne
Vad betyder det här?
- Bästa fall: hur tiden växer med listans storlek n när indata är den lättaste för den här algoritmen.
- Genomsnitt: hur tiden brukar växa med n. Med n² tar dubbla antalet värden ungefär fyra gånger så lång tid. n log n växer mycket långsammare.
- Värsta fall: tillväxten på den svåraste indatan. Viktigt när hastigheten aldrig får sjunka.
- Minne: hur mycket extra minne som behövs utöver listan. 1 betyder några variabler, n betyder en kopia av listan.
- Stabil: två lika värden behåller sin ursprungliga ordning. Viktigt när man sorterar poster efter ett fält.
- Utan extra minne: sorterar inuti själva listan, utan en andra lista.
- jämförs
- flyttas
- i handen
- sorterad del
- på slutgiltig plats
Tryck på Spela upp: linjerna visar hur kostnaden växer
Tryck på Spela upp eller gå igenom algoritmen steg för steg.
Blanksteg: spela upp eller pausa. Vänster och höger pil: steg. Home och End: hoppa.
Prova det här: Välj en nästan sorterad lista. Nästan inget behöver flyttas, så den blir klar på väldigt få steg.
Så fungerar det
Den vänstra delen är alltid sorterad. Nästa värde lyfts ut. Varje större värde i den sorterade delen flyttas en plats åt höger, och sedan läggs värdet i luckan. Så sorterar många människor spelkort på handen.
När det är ett bra val
Ett bra val för korta listor och för listor som nästan är sorterade, där den är mycket snabb. Riktiga sorteringsbibliotek använder den för små bitar av en lista inuti snabbare metoder.