Urvalssortering

Från Wikipedia
Hoppa till navigering Hoppa till sök
Animation av urvalssortering.

Urvalssortering (selection sort) ä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 talet. (N - 1 jämförelser)
  2. Flytta talet till den första positionen
  3. Sök efter näst minsta talet. (N - 2 jämförelser)
  4. Flytta talet det till 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²).