Shellsort

SHELLSORT

PROBLÉM

Je dáno pole A. obsahující N prvků. Výsledkem třídění v místě je přerovnání prvků pole A. takovým způsobem, že platí
A.1<=A.2<=...<=A.N

ALGORITMUS

Nejprve přerovnáme prvky pole aby všechny prvky s posunutím H.1 byly utříděné. Pak je přerovnáme tak, aby byly utříděné prvky s posunutím H.2 (H.1>H.2) atd. až nakonec utřídíme celé pole (tj. utřídíme všechny prvky s posunutím jedna). D. L. Shell, autor algoritmu, doporučil počáteční volbu H=N%2 a dále pak užití vzorce H=H%2. Posloupnost H., která se v praxi nejlépe osvědčuje, je
H=...,1093,364,121,40,13,4,1
tj. H = (3**K-1)/2, generováno vzorcem H=3*H+1 s počáteční hodnotou H=1. Časová složitost tohoto algoritmu je v nejhorším případě O(N**(3/2); v průměru pak O(N**1.25).

PRAXE

Následující tabulka porovnává 4 algoritmy třídění. Pole A. obsahuje celá čísla z intervalu 1 až Max, kde Max=10,100,1000,40000.

Doba výpočtu v sekundách pro N=10 000
Algoritmus Max = 100 Max = 1000 Max = 40000 Max = 99999

QUICKSORT 4.66 4.53 4.89 4.59

HEAPSORT 10.26 10.67 11.58 11.18

SHELLSORT 7.45 8.89 10.58 10.13

COUNTING_SORT 1.88 1.95 7.93 31.85

IMPLEMENTACE

Jednotka: nerekurzívní vnitřní podprogram

Globální proměnné: pole A. libovolných prvků

Parametr: přirozené číslo N - počet prvků v poli A.

Výsledek: Přeuspořádá vstupní pole tak, že platí
A.1<=A.2<=...<=A.N

SHELLSORT: procedure expose A.
parse arg N
H = 1
do until H > N; H = 3 * H + 1; end
do until H = 1
  H = H % 3
  do I = H + 1 to N
    V = A.I; J = I; JmH = J - H
    do while A.JmH > V
      A.J = A.JmH; J = J - H
      if J <= H then leave
      JmH = J - H
    end
    A.J = V
  end
end
return

SOUVISLOSTI

Třídění
     Distribuční třídění
     Heapsort
     Quicksort
Slučování

Literatura
Rich R. P. Internal Sorting Methods Illustrated with PL/1 Programs

Prentice Hall, Inc., Engelwood Cliffs, 1972

Sedgewick R. Algorithms

Addison-Wesley, Reading, Massachusetts, 1984

Poděkování
Změnil jsem test z Max=10 ... 40000 na Max=100 ... 99999. Díky za nápad patří Walteru Pachlovi z Vídně.

Poznámka
Tento test běžel v prostředí Windows 2000 Professional na počítači se 132MB RAM a procesorem typu x86Family 6 Mode 6 Stepping 5.