Innsettingssortering

Innsettingssortering er en enkel sorteringsalgoritme som bygger den endelige sorterte listen ved å sette inn hvert nytt element i riktig posisjon i den allerede sorterte delen. Algoritmen starter med det første elementet som sortert og fortsetter gjennom hele listen.

Arbeidsmåte: For hvert nytt element k i den uordnede delen går algoritmen bakover i den sorterte delen og sammenligner k med elementene der. Den flytter større elementer ett posisjon til høyre for å gjøre plass, og setter til slutt inn k i den korrekte posisjonen.

Fordeler og egenskaper: Algoritmen er stabil og in-place, dvs. den krever bare konstant ekstra minne. Den er enkel å implementere og effektiv for små datasett eller listene som allerede er nesten sorterte.

Kompleksitet: Tidsmessig har innsettingssortering verste fall og gjennomsnittlig O(n^2), mens beste fall er O(n) når listen allerede er sortert. Romlig bruker den O(1) ekstra plass.

Varianter og spesialtilfeller: Noen implementasjoner bruker binær søk for å finne innsettingsposisjonen, noe som reduserer antall sammenligninger, men antallet flyttinger av elementer forblir O(n). Den grunnleggende metoden beholder samtidig sin stabilitet.

Bruksområder: Passer godt for små lister eller lister som allerede er nesten sorterte, og brukes ofte i undervisning for å illustrere grunnleggende sorteringsprinsipper. Ikke ideell for store datasett uten spesielle tilpasninger.