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
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.
