Insättningssortering
 |
Den här artikeln behöver källhänvisningar för att kunna verifieras. (2023-07) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan. |
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 , 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 med exemplet
- Jämför det nya talet med det sista talet i listan
- Om det nya är större, lägg det sist i listan
- Flytta annars det sista talet ett steg bakåt och jämför igen
- 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
- Upprepa för varje nytt tal