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 1Max, 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
Třídění
     Distribuční třídění
     Shellsort
     Quicksort
     Slučování

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.


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.

 


obálka obsah index hlavní

změněno 12. dubna 2018
Copyright © 2000-2018 Vladimír Zábrodský, RNDr.

mail