Insättningssortering

Insättningssortering

Sorteringsalgoritm, stabil sorteringsalgoritm, parvis jämförelse, adaptiv sortering, in-place-algoritm, online-algoritm

Tids­komp­lex­i­tet i värsta fall	$O(n^{2})$
Tids­komp­lex­i­tet i bästa fall	$O(n)$
Tids­komp­lex­i­tet i medel	$O(n^{2})$
Rums­komp­lex­i­tet i värsta fall	$O(1)$

Exempel på insättningssortering med åtta element.

Insättningssortering, eller instickssortering, är en av de enklare sorteringsalgoritmer som finns tillgängliga inom datalogi. I praktiken använder man ofta snabbare sorteringsalgoritmer, men om listan redan är delvis sorterad kan den dock vara effektiv.

Komplexiteten för insättningssortering är i allmänhet $O(n^{2})$, där n är antalet element, om listan redan är någorlunda sorterad från början är dock insättningssortering en av de snabbare algoritmerna.

Exempel

Algoritmen kan beskrivas med exemplet

1. Jämför det nya talet med det sista talet i listan
2. Om det nya är större, lägg det sist i listan
3. Flytta annars det sista talet ett steg bakåt och jämför igen
4. Flytta så många tal som behövs ett steg bakåt för att sätta in det nya talet på rätt plats
5. Upprepa för varje nytt tal