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 $k\in \mathbb {N}$ .^[1]

Algoritmus

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

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

Č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

↑ 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

Commons ponúka multimediálne súbory na tému Counting sort

Externé odkazy

Simulácia Counting sortu

[1] 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).

[ItoA-2] 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)

[bak-3] ZEMIANEK, Juraj. Triediace algoritmy (Bakalárska práca). Bratislava: 2007.

[1]

[2]

[3]