DISTRIBUČNÍ TŘÍDĚNÍ
PROBLÉM
Uspořádat pole A. obsahující N celých čísel z intervalu 1 až K.
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 1 až K. 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 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: vnitřní podprogram
Globální proměnné: pole A. celých čísel z intervalu 1 až K
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
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.
