DISTRIBUČNÍ TŘÍDĚNÍ

PROBLÉM
Uspořádat pole A. obsahující N celých čísel z intervalu 1K.

ALGORITMUS
Distribuční třídění objevil Harold H. Seward v roce 1954. Je použitelné jen v případě, že každý prvek pole je celé číslo z intervalu 1K. Pokud K=O(N), pak časová složitost tohoto algoritmu je O(N). Algoritmus využívá pracovní pole.

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: vnitřní podprogram
 
Globální proměnné: pole A. celých čísel z intervalu 1K
 
Parametry: přirozené číslo N - počet prvků v A., přirozené číslo K
 
Výsledek: Přeuspořádá vstupní pole tak, že platí

A.1<=A.2<=...<=A.N
 

COUNTING_SORT: procedure expose A.
parse arg N, K
C. = 0
do J = 1 to N
  Aj = A.J; C.Aj = C.Aj + 1
end
do J = 2 to K
  Jm1 = J - 1; C.J = C.J + C.Jm1
end
do J = N to 1 by -1
  Aj = A.J; CAj = C.Aj; B.CAj = A.J
  C.Aj = CAj - 1
end
do J = 1 to N; A.J = B.J; end
return

 

SOUVISLOSTI
Třídění
     Heapsort
     Shellsort
     Quicksort
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

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.