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 .

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).
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). 

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).. 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

Iné projekty

Externé odkazy 
 Simulácia Counting sortu

Triediacie algoritmy