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 ${\displaystyle 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 := 0; //inicializácia poľa C na 0
  for j := 1 to length(A) do 
    Cj := CAj + 1;  // Ci teraz obsahuje počet výskytov prvku i v poli A
  for i := 1 to k do 
    Ci := Ci + Ci – 1; // Ci teraz obsahuje počet prvkov menších alebo rovných ako i
  for j := length(A) downto 1 do
  begin
    BCAj := Aj; // B je utriedená množina
    CAj := CAj – 1;
  end;
end;

Príkladupraviť | 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

Vlastnostiupraviť | 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á.

Referencieupraviť | upraviť zdroj

Iné projektyupraviť | upraviť zdroj

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

Externé odkazyupraviť | upraviť zdroj

• Simulácia Counting sortu