välj - pussel på nätet

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,

Sök igenom listan efter minsta talet. (N - 1 jämförelser)

Flytta talet till den första positionen

Sök efter näst minsta talet. (N - 2 jämförelser)

Flytta talet det till andra positionen

och så vidareTotalt krävs

N

(

N

−

1

)

/

2

{\displaystyle N(N-1)/2}

jämförelser och

N

−

1

{\displaystyle N-1}

byten, oberoende av hur osorterad listan är från början. Algoritmens komplexitet blir

O

(

N

2

)

{\displaystyle O(N^{2})}

.