Insättningssortering

Från Rilpedia

Version från den 17 maj 2009 kl. 13.27 av SilvonenBot (Diskussion)
(skillnad) ← Äldre version | Nuvarande version (skillnad) | Nyare version → (skillnad)
Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif
icon_anmal.gif
rp-wp-sv.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.

Hämtad från "https://sv.rilpedia.org/wiki/Ins%C3%A4ttningssortering"
Personliga verktyg