Insättningssortering

Från Wikipedia
Hoppa till: navigering, sök
Exempel på insättningssortering med åtta element.

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.

Komplexiteten för insättningssortering är i allmänhet O(n²), 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[redigera | redigera wikitext]

Algoritmen kan beskrivas genom följande exempel:

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