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 1Max, 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.


Obálka Obsah Index Hlavní stránka

změněno 11. září 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.