Quicksort

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

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.