Zaradenie a popis

Selection Sort je triediaci algoritmus, ktorý realizuje triedenie priamym výberom.
Vychádza z predpokladu, že najmenší prvok môžeme zaradiť priamo na začiatok triedeného poľa, najmenší prvok zo zvyšku poľa zase na jeho začiatok atď.
Podľa toho, či triedi prvky vzostupne/zostupne, sa môže označovať ako MinSort/MaxSort.

^ TOP

Motivácia a špecifikácia

Máme v poli uloženú postupnosť prvkov. Cieľom je usporiadať túto postupnosť vzostupne.
Vstup: pole A, ktoré je naplnené náhodnými hodnotami
Výstup: utriedené pole A

^ TOP

Myšlienka algoritmu

V prvom kroku sa vyberie najmenší prvok postupnosti a preradí sa na prvé miesto. V ďalšom kroku sa vyberie najmenší prvok zostávajúcej postupnosti n-1 prvkov a preradí sa na druhé miesto. Algoritmus takto pokračuje, až po n krokoch je postupnosť utriedená.

^ TOP

Vizualizácia

Červeným je vyznačený najmenší prvok z neutriedenej časti poľa.
Sivým sú označené prvky z utriedenej časti poľa.
Bielym sú označené prvky z neutriedenej časti poľa.

^ TOP

Zápis algoritmu

  procedure SelectionSort(var A: array of Integer);
  var
    I, J, T: Integer;
  begin
    for I := Low(A) to High(A) - 1 do
     for J := High(A) downto I + 1 do
       if A[I] > A[J] then
       begin
         T := A[I];
         A[I] := A[J];
         A[J] := T;
       end;
  end;       
      
      

^ TOP

Vlastnosti algoritmu

Časová zložitosť algoritmu je v priemernom prípade je O(n2).
V najhoršom prípade je časová zložitosť tiež O(n2).
Algoritmus pracuje in situ (na mieste) a je stabilný.
Selection Sort je výnimočný tým, že počet vykonaných operácií nie je nijako ovplyvnený počiatočným usporiadaním prvkov. Taktiež vykonáva optimálnych n výmien a teda iba O(n) zápisov na disk. Ak je teda zápis na disk časovo nákladná operácia, môže byť Selection Sort dobrou voľbou.

^ TOP

Experimentovanie

Department of Computer Science, University of British Columbia, Canada
Java applety rôznych triediacich algoritmov.
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

Department of Electrical and Computer Engineering, University of New Brunswick, Canada
Selection sort spracovaný do appletu.
http://www.ece.unb.ca/brp/lib/java/selectionsort/

^ TOP