Urvalssortering

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

Urvalssortering (selection sort) är en av de enklare sorteringsalgoritmer som finns tillgängliga inom datalogi.

Algoritmen kan beskrivas genom följande exempel:

Vi tänker oss att vi ska sortera en lista med N tal.

  1. Sök igenom listan efter minsta talet. (N-1 jämförelser)
  2. Flytta det till första positionen.
  3. Sök efter näst minsta talet. (N-2 jämförelser)
  4. Flytta det till andra positionen.
  5. osv

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²).