Select Sort

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 P
Algoritmus 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]);
    } 
}

Celý kód ke stažení zde.

Související