Urvalssortering

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.

Urvalssortering är en av de enklare sorteringsalgoritmer som finns tillgängliga inom datalogi.

Algoritmen kan beskrivas med ett exempel. En lista med N tal skall sorteras,

1. Sök igenom listan efter minsta elementet. (N - 1 jämförelser)
2. Byt elementet mot elementet på den första positionen
3. Sök efter näst minsta talet. (N - 2 jämförelser)
4. Byt elementet mot elementet på den andra positionen
5. och så vidare

Totalt krävs ${\displaystyle N(N-1)/2}$ jämförelser och ${\displaystyle N-1}$ byten, oberoende av hur osorterad listan är från början. Algoritmens komplexitet blir ${\displaystyle O(N^{2})}$.