Urvalssortering

Animation av urvalssortering.

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 $N(N-1)/2$ jämförelser och $N-1$ byten, oberoende av hur osorterad listan är från början. Algoritmens komplexitet blir $O(N^2)$.