Insättningssortering

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif

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:

  1. Jämför nya talet med sista talet i listan.
  2. Om nya är större, lägg det sist i listan.
  3. Puta annars bak sista talet ett pinnhål och jämför igen.
  4. Puta 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.

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.

Personliga verktyg