QUICKSORT

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
Slavný třídící algoritmus C.A.R Hoara s časovou složitostí O(N*lgN) v průměru a O(N**2) v nejhorším případě.

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
 

QUICKSORT: procedure expose A.
parse arg N
S = 1; StackL.1 = 1; StackR.1 = N
do until S = 0
  L = StackL.S; R = StackR.S; S = S - 1
  do until L >= R
    I = L; J = R; P = (L + R) % 2
    if A.L > A.P
      then do; W = A.L; A.L = A.P; A.P = W; end
    if A.L > A.R
      then do; W = A.L; A.L = A.R; A.R = W; end
    if A.P > A.R
      then do; W = A.P; A.P = A.R; A.R = W; end
    X = A.P
    do until I > J
      do I = I while A.I < X; end
      do J = J by -1 while X < A.J; end
      if I <= J
        then do
          W = A.I; A.I = A.J; A.J = W
          I = I + 1; J = J - 1
        end
    end
    if J - L < R - I
      then do
        if I < R
          then do
            S = S + 1; StackL.S = I; StackR.S = R
          end
        R = J
      end
      else do
        if L < J
          then do
            S = S + 1; StackL.S = L; StackR.S = J
          end
        L = I
      end
  end /* until L >= R */
end /* until S = 0 */
return
 

Máme-li uspořádat prvky pole tak, aby tvořily nerostoucí posloupnost, změníme jen červeně vyznačené příkazy:


      do I = I while A.I > X; end
      do J = J by -1 while X > A.J; end

 

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

Literatura
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990
Sedgewick R. Algorithms
Addison-Wesley, Reading, Massachusetts, 1984
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.


Obálka Obsah Index Hlavní stránka

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