Zaradenie a popis

Shell Sort je triediaci algoritmus, ktorý realizuje triedenie priamym vkladaním so zmenšovaním kroku.
Je to vlastne zlepšenie triedenia vkladaním a bublinkového triedenia. Táto metóda je jedna z najrýchlejších pre triedenie menších postupností (1000 a menej prvkov).

^ 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

Postupne sa porovnávajú prvky vzdialené od seba i miest, v prípade potreby sa vymenia. Zníži sa i (spôsobom popísaným nižšie) a opakuje sa postup. Nakoniec je i=1 a prebehne obyčajné triedenie vkladaním. Triediaci algoritmus nekladie žiadne špecifické požiadavky na postupnosť dĺžok krokov. Musí však platiť veta: Ak je h1, h2, … ht postupnosť krokov, tak platí ht = 1 a zároveň hi+1 < hi. Ukazuje sa však, že niektoré postupnosti vedú k lepšej časovej zložitosti algoritmu.

^ TOP

Vizualizácia

Spoločnou farbou sú označené prvky, ktoré sa porovnávajú. V prvom kroku sú vzdialené 5 miest, v druhom 3 a v poslednom 1.

^ TOP

Zápis algoritmu

  procedure ShellSort(var f:array of integer);
  var
    i, j, h, v, N: integer;
  begin
    N := length(f);
    h := 1;
    repeat
      h := ( 3 * h ) + 1; //výber krokov
    until h > N;
    repeat
      h := ( h div 3 );
      for i := ( h + 1 ) to N do begin
        v := f[i];
        j := i;
        while ( ( j > h ) and ( f[j-h] > v ) ) do begin
          f[j] := f[j - h];
          dec( j, h );
        end;
        f[j] := v;
      end;
    until
      h = 1;
  end;      
      

^ TOP

Vlastnosti algoritmu

Pôvodné triedenie vkladaním je efektívne, ak je pole prvkov takmer utriedené. V Shell Sort-e každý ďalší prechod profituje z predchádzajúcich triedení – vzhľadom na to, že každé triedenie s krokom i kombinuje výsledky predchádzajúcich triedení. Musí intuitívne platiť podmienka, že ak triedime s krokom i postupnosť, ktorá bola utriedená s krokom k, tak táto ostáva utriedená s krokom k. Je tiež zrejmé, že akákoľvek postupnosť krokov bude prijateľná, pretože v najhoršom prípade urobí všetku triediacu prácu urobí posledný prechod.

Časová zložitosť algoritmu závisí od použitých krokov pri triedení.
Pri použití Shellovej postupnosti (začína na polovičnej veľkosti poľa a zakaždým sa delí 2) je to O(n2).
Hibbardova postupnosť: (2k - 1) má časovú zložitosť O(n3/2).
Sedgewickove postupnosti: (9(4i) - 9(2i) + 1) alebo (4i + 1 + 3(2i) + 1 ) majú časovú zložitosť O(n4/3).
Existujú aj postupnosti dosahujúce zložitosť O(n.log2n), ale existencia postupnosti, ktorá prináša v najhoršom prípade časovú zložitosť O(n.logn) zostáva otázna.

^ 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

School of Computing and Information Sciences, Florida International University, USA
Prehľadný java applet na experimentáciu so Shell sortom.
http://www.cs.fiu.edu/~weiss/Shellsort.html

^ TOP