Urvalssortering
Hoppa till navigering
Hoppa till sök
Urvalssortering
Tidskomplexitet i värsta fall | ![]() | |
---|---|---|
Tidskomplexitet i bästa fall | ![]() | |
Tidskomplexitet i medel | ![]() | |
Rumskomplexitet i värsta fall | ![]() |
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 elementet. (N - 1 jämförelser)
- Byt elementet mot elementet på den första positionen
- Sök efter näst minsta talet. (N - 2 jämförelser)
- Byt elementet mot elementet på den andra positionen
- och så vidare
Totalt krävs jämförelser och byten, oberoende av hur osorterad listan är från början. Algoritmens komplexitet blir .