Zobrazenie zdroja stránky 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 <math>k \in \mathbb N</math>.<ref>{{Citácia knihy
  |priezvisko=Edmonds
  |meno=Jeff
  |strany=72–75
  |titul=How to Think about Algorithms
  |kapitola=5.2 Counting Sort (a Stable Sort)
  |vydavateľ=Cambridge University Press
  |rok=2008
  |isbn=978-0-521-84931-9
  | jazyk= po anglicky}}.</ref> 

==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''' <br />
Pole A - vstupná množina<br />
Pole B - výstup (utriedená množina)<br />
Pole C - pomocné pole, v ktorom sa ukladá počet výskytov vstupných prvkov<br />

<source lang="delphi">
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;
</source>


==Príklad==
Majme vstupnú množinu prvkov [3,1,5,2,1,5,1].<br />
Do pomocného poľa si uložíme počet výskytov jednotlivých prvkov<br />
 1 – 3x
 2 – 1x
 3 – 1x
 5 – 2x

Prepočítame ich na hranice prvkov:<br />
 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)<br />
 [ , ,1, , , , ]

Upravíme pomocné pole a hranice prvkov:<br />
 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).<ref name="ItoA">{{Citácia elektronického dokumentu
 | priezvisko = Cormen | meno = Thomas H. | odkaz na autora = Thomas H. Cormen
 | priezvisko2 = Leiserson | meno2 = Charles E. | odkaz na autora2 = Charles E. Leiserson
 | priezvisko3 = Rivest | meno3 = Ronald L. | odkaz na autora3 = Ron Rivest
 | spoluautori = ai.
 | titul = Introduction to Algorithms 
 | kapitola = 8.2 Counting Sort
 | edícia = 2nd
 | isbn = 0-262-03293-7
 | strany = 168–170
 | vydavateľ = [[MIT Press]] and [[McGraw-Hill]]
 | dátum vydania = 2001
 | jazyk = po anglicky}}</ref>
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). <ref name="bak">{{Citácia elektronického dokumentu
  | priezvisko = Zemianek
  | meno = Juraj
  | odkaz na autora = 
  | titul = Triediace algoritmy (Bakalárska práca)
  | url = 
  | dátum vydania = 2007
  | dátum aktualizácie = 
  | dátum prístupu = 
  | vydavateľ = 
  | miesto = Bratislava}} </ref>

'''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).<ref name="ItoA"/>. 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 ==
{{referencie}}

== Iné projekty ==
 {{projekt|commons=Category:Sort algorithms}}

== Externé odkazy ==
* [http://www.cs.miami.edu/~burt/learning/Csc517.091/workbook/countingsort.html Simulácia Counting sortu]

{{Triediace algoritmy}}
[[Kategória:Triediacie algoritmy]]