Udtagelsessortering

Fra Wikipedia, den frie encyklopædi

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ætter dem på deres rette plads.

[redigér] 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 søgningmetode, som er anvendt. Algoritmen virker på den måde, at den starter 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).

Algoritem 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

På figuren er den sorterede liste vist med gråt mens den usorterede liste er vist med røde og hvide felter.

[redigér] 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.