Urvalssortering

Från Wikipedia
Hoppa till navigering Hoppa till sök
Urvalssortering
Selection sort animation.gif
Sorteringsalgoritm Redigera
Tids­komp­lex­i­tet i värsta fall Redigera
Tids­komp­lex­i­tet i bästa fall Redigera
Tids­komp­lex­i­tet i medel Redigera
Rums­komp­lex­i­tet i värsta fall Redigera
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 jämförelser och byten, oberoende av hur osorterad listan är från början. Algoritmens komplexitet blir .