Counting sort
Counting sort je triediaci algoritmus, ktorý v lineárnom čase utriedi prvky v konečnej množine. Všetky prvky sú celé čísla z intervalu <0; k-1> pre .[1]
Algoritmus
[upraviť | upraviť zdroj]Pre každý prvok x vo vstupnej množine sa určí počet prvkov, ktoré sú rovné ako daný prvok x. Tento údaj sa uloží do pomocného poľa. Ku každej položke v pomocnom poli sa následne pripočíta počet výskytov predchádzajúcich položiek. Takýmto spôsobom sa získa presná pozícia hranice, ktorá sa využije na priame umiestnenie prvku x vo výstupnom zoradenom poli. Algoritmus začne sprava prechádzať neutriedené prvky vo vstupnom poli a pre každý prvok sa pozrie na jeho hornú hranicu, ktorú má uloženú v pomocnom poli. Na túto pozíciu ho uloží do výstupného poľa a následne toto číslo zníži o 1. Obdobným spôsobom prejde celé vstupné pole sprava doľava a výstup – utriedené prvky - sa budú nachádzať vo výstupnom poli.
Pseudokód
Pole A - vstupná množina
Pole B - výstup (utriedená množina)
Pole C - pomocné pole, v ktorom sa ukladá počet výskytov vstupných prvkov
procedure Counting_Sort;
begin
for i := 0 to k do
C[i] := 0; //inicializácia poľa C na 0
for j := 1 to length(A) do
C[A[j]] := C[A[j]] + 1; // C[i] teraz obsahuje počet výskytov prvku i v poli A
for i := 1 to k do
C[i] := C[i] + C[i – 1]; // C[i] teraz obsahuje počet prvkov menších alebo rovných ako i
for j := length(A) downto 1 do
begin
B[C[A[j]]] := A[j]; // B je utriedená množina
C[A[j]] := C[A[j]] – 1;
end;
end;
Príklad
[upraviť | upraviť zdroj]Majme vstupnú množinu prvkov [3,1,5,2,1,5,1].
Do pomocného poľa si uložíme počet výskytov jednotlivých prvkov
1 – 3x 2 – 1x 3 – 1x 5 – 2x
Prepočítame ich na hranice prvkov:
1 – 3 2 – 4 (tri výskyty prvku 1 a jeden výskyt prvku 2) 3 – 5 5 – 7
Zaradenie prvého prvku (ideme sprava doľava)
[ , ,1, , , , ]
Upravíme pomocné pole a hranice prvkov:
1 – 2x (hranica:2) 2 – 1x (hranica:4) 3 – 1x (hranica:5) 5 – 2x (hranica:7)
Zaradenie ostatných prvkov (analogicky)
[ , ,1, , , ,5] [ ,1,1, , , ,5] [ ,1,1,2, , ,5] [ ,1,1,2, ,5,5] [1,1,1,2, ,5,5] [1,1,1,2,3,5,5] [1,1,1,2,3,5,5]
Vlastnosti
[upraviť | upraviť zdroj]Časová zložitosť: Inicializácia poľa C – nastavenie prvkov na 0 a jeden ďalší prechod týmto poľom trvajú O(k), algoritmus prejde navyše dvakrát pole A, to trvá O(n). Takto je celkový beh v čase O(n + k).[2] Za predpokladu, že rozsah 1..k nie je väčší než n, teda možno uvažovať, že k = O(n) a teda je potom celkový čas behu countingsortu O(n). [3]
Pamäťová zložitosť: Counting sort využíva polia dĺžok k+1 a n. Celková pamäťová zložitosť preto je O(n + k).[2]. Za rovnakého predpokladu, ako je uvedený pri časovej zložitosti, je pamäťová zložitosť O(k).
Stabilita: Countingsort je stabilné triedenie. Znamená to, že prvky rovnakej hodnoty na vstupe budú v rovnakom poradí na výstupe. Je to z toho dôvodu, že nie je založený na porovnaní. Avšak keby sme pole začali triediť smerom zľava doprava, výsledná množina by nebola stabilná.
Referencie
[upraviť | upraviť zdroj]- ↑ EDMONDS, Jeff. How to Think about Algorithms. [s.l.] : Cambridge University Press, 2008. ISBN 978-0-521-84931-9. Kapitola 5.2 Counting Sort (a Stable Sort), s. 72–75. (po anglicky).
- ↑ a b CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L., ai. Introduction to Algorithms. MIT Press and McGraw-Hill, 2001. (2nd.) Kapitola 8.2 Counting Sort, s. 168–170. ISBN 0-262-03293-7. (po anglicky)
- ↑ ZEMIANEK, Juraj. Triediace algoritmy (Bakalárska práca). Bratislava: 2007.
Iné projekty
[upraviť | upraviť zdroj]
Commons ponúka multimediálne súbory na tému Counting sort
