Selection sort je jeden z nejjednodušších (naivní) třídích algoritmů. Má časovou složitost Θ(n2) a obecně bývá pomalejší než insertion sort.
Princip
- Založen na opakovaném vybírání nejmenšího prvku.
- Vstupní posloupnost se rozdělí nalevou seřazenou a pravou neseřazenou část.
- Na počátku je levá část prázdná a pravá část je celá vstupní posloupnost.
- Z neseřazené pravé části se vybere minimum a prohodí se s jejím prvním prvkem, tj. přímo za seřazenou část.
- Po vložení minima na začátek neseřazené části se posune hranicemezi seřazenou a neseřazenou částí o jednu pozici doprava
- Tento postup provádíme, dokud se pravá neseřazená částnezmenší na 1 prvek.
Pseudokód
Vstup: pole P[1 … n] Výstup: vzestupně seřazené pole PAlgoritmus SelectSort
Pro i := 1 … n:
m:=i // m je index momentálního minima pravé části
Pro j:= (i + 1) … n:
Pokud P[j] < P[m]:
m := j
Prohoď P[i] a P[m]
Složitost
Korektně seřadí n-prvkové pole v čase O(n2) a je nestabilní, in-place, datově necitlivý.
Důkaz
- Invariant: Po i-té iteraci cyklu na řádcích (1)-(6)je vlevo seřazená posloupnost délky i a vpravo zbývá n−i neseřazených prvků, které jsou ≥ než čísla v levé části.
- V každém kroku se nalezne minimum ze zbývajících prvkůvpravo a přesune se na konec levé části.
- V i-té iteraci trvá vyhledání minimaO(i)operací, což dávácelkovou časovou složitost O(n+ (n−1) +···+ 1) =O(n2).
- Z důvodu prohazování nesousedních prvků je možné změnitpořadí prvků se stejnou hodnotou, čili je nestabilní.
Implementace v C
void selectionSort(int a[], int n) { int j, tmp, min; for (int i=0; i<(n - 1); i++) { min = i; for (j=i+1; j<n; j++) { if (a[j]<a[min]) min = j; } swap(&a[i], &a[min]); } }