Urvalssortering

Urvalssortering

Sorteringsalgoritm

Tids­komp­lex­i­tet i värsta fall	$O(n^{2})$
Tids­komp­lex­i­tet i bästa fall	$O(n^{2})$
Tids­komp­lex­i­tet i medel	$O(n*n)$
Rums­komp­lex­i­tet i värsta fall	$O(1)$

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})$.