Insättningssortering
Från Rilpedia
Texten från svenska Wikipedia
Insättningssortering (Insertion sort) ä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 vara bra.
Algoritmen kan beskrivas genom följande exempel:
- Jämför nya talet med sista talet i listan.
- Om nya är större, lägg det sist i listan.
- Puta annars bak sista talet ett pinnhål och jämför igen.
- Puta bak så många tal som behövs för att sätta in nya talet på rätt plats.
- Upprepa för varje nytt tal.
Komplexiteten för insättningssortering är i allmänhet O(N²), om listan redan är någorlunda sorterad från början är dock insättningssortering en av de snabbare algoritmerna.
