HEAPSORT
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
Heapsort J. W. J. Williamse je třídící algoritmus, který má v nejhorším i v průměrném případě tutéž časovou složitost O(N*lgN).
PRAXE
V průměru je HEAPSORT asi dvakrát pomalejší než QUICKSORT, ale při jeho použití máme jistotu, že v nejhorším případě nedojde ke katastrofické degradaci výkonu, jako je tomu u QUICKSORTu. Následující tabulka porovnává 4 algoritmy třídění. Pole A. obsahuje celá čísla z intervalu 1 až Max, kde Max=100,1000,40000,99999.
| Doba výpočtu v sekundách pro N=10000 |
| 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: 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
HEAPSORT: procedure expose A.
parse arg N
do I = N % 2 to 1 by -1
call SIFT I, N
end
do I = N to 2 by -1
W = A.1; A.1 = A.I; A.I = W
call SIFT 1, I - 1
end
return
SIFT: procedure expose A.
parse arg L, R
I = L; W = A.I; J = 2 * I
Jp1 = J + 1
if J < R then
if A.J < A.Jp1 then J = Jp1
do while J <= R
if W >= A.J then leave
A.I = A.J; I = J; J = 2 * I
Jp1 = J + 1
if J < R then
if A.J < A.Jp1 then J = Jp1
end
A.I = W
return
|
SOUVISLOSTI
Literatura
Wirth N. Algorithms and data structure
New Jersey, Prentice Hall, Inc., Engelwood Cliffs, 1986
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.
James Barbetti mi poslal podprogram HEAPSORT_RADIX3 napsaný ve Visual Basicu. Komentuje ho takto:
Místo ~ 2*N*log(N)/log(2) porovnání a výměn dostaneme v průměru ~ 2*log(N)/log(3) + 2*N porovnání a
~ N*log(N)/log(3) + N výměn.
HEAPSORT_RADIX3: procedure expose A.
parse arg N
do R = (N+1)%3 to 1 by -1
call SiftDown A.R, N, R
end
do R = N to 2 by -1
V = A.R; A.R = A.1
call SiftDown V, (R - 1), 1
end
return
SIFTDOWN: procedure expose A.
V = ARG(1); Count = ARG(2); I = ARG(3)
J = I
do forever
K = J * 3 - 1
if K < Count - 1
then do
Kp1 = K + 1; Kp2 = K + 2
if A.K < A.Kp1 then
if A.Kp1 < A.Kp2 then K = Kp2
else K = Kp1
else if A.K < A.Kp2 then K = Kp2
end
else do
if K < Count
then do
Kp1 = K + 1
if A.K < A.Kp1 then K = Kp1
end
else if Count < K then leave
end
A.J = A.K
J = K
end
K = J
do while K > I
J = (K + 1) % 3
if A.J > V then leave
A.K = A.J
K = J
end
A.K = V
return
|
Poděkování
Děkuji Jamesu Berbettimu za (spíše teoreticky) zajímavý programový kód.
