Udtagelsessortering

Udtagelsessortering (eng. selection sort) er for de fleste mennesker den mest oplagte måde at sortere på. Grundidéen er meget simpel, og mange mennesker anvender denne form for sortering i deres dagligdag. Udtagelsessortering anvender søgning til at finde de forskellige elementer og indsætte dem på deres rette plads.

Algoritmen

Udtagelsessorteringsalgoritmen illustreres ved et eksempel. På figuren svarer de grå felter til de elementer der er sorteret færdigt, og de røde felter svarer til de elementer, som er fundet ved hjælp af den anvendte søgningsmetode. Algoritmen begynder med at søge efter elementet med den mindste værdi, og derefter byttes der om på denne værdi og værdien i felt nr. 1 i listen, figur (a)-(b), derefter søger den i den resterende liste og finder det af de resterende elementer med mindst værdi, hvorefter den ombyttes værdien i felt nr. 2, figur (b)-(c). Proceduren gentages for alle elementerne; i den sidste iteration er det ikke nødvendigt at søge efter det sidste element, da det allerede er på plads. Nederst på illustrationen er den færdigsorterede liste vist, figur (f).

Algoritmen kan også formuleres rekursivt for en liste med N elementer:

1. Hvis N er mindre end 2 så stop.
2. Find det mindste element i listen.
3. Byt om på det mindste element og det første element i listen.
4. Lav udtagelsessortering på elementerne 2 til N i listen

Beregningskompeksiteten

Udtagelsessorterings-tidskompleksitet domineres af den lineære søgning i hver iteration. Der skal gennemføres N gennemløb af listen og listen skal læses helt, da man ikke på forhånd ved, hvor det mindste element er. I gennemsnit vil listens længde være N/2. I starten er den på N og til sidst på 1. Køretiden vil derfor være Θ(N²/2) eller Θ(N²) når konstanten er fjernet.