Skip to main content.

Zaradenie a popis

Counting sort je triediaci algoritmus, ktorý pracuje v čase O(n). Nie je to teda triedenie porovnávaním. Využíva to, že dopredu sa vie rozsah čísel v poli A, ktoré sa má triediť. Používa pomocné pole C, ktoré je veľké podľa tohto rozsahu (to znamená maximálna hodnota mínus minimálna hodnota plus jedna). Týmto sa algoritmus stáva nepraktickým pre veľké rozsahy čísel kvôli narastajúcej časovej a pamäťoje zložitosti. Counting sort je vhodný napríklad na triedenie čísel z rozsahu od 0 do 100, ale nie je vhodný na abecedné utriedenie menného zoznamu. Môže však byť vhodne použitý v algoritme triedenia Radix sort, keď je tento rozsah príliš veľký na triedenie priamo Counting sortom.

^ TOP

Myšlienka algoritmu

Vytvorí sa pole C, ktorého veľkosť je od minima po maximum triedeného poľa A. V prípade, že je možná len pevná indexácia (napríklad so začiatkom len v 0), musia byť hodnoty z A mapované na C. Ak ide len o funkciu, kde sa od každého prvku odčíta minimum poľa A, aby sa získal zodpovedajúci index v poli C, triedenie sa volá Counting sort (ak sa prvky mapujú zložitejšou funkciou, algoritmus triedenia je Bucket sort). Ak priamo nepoznáme maximum a minimum, je potrebné tieto hodnoty zistiť jedným prechodom poľa A.

Každý index i v poli C je nasledovne použitý na spočítanie koľko prvkov poľa A má hodnotu menšiu ako i. Počty uložené v C sú potom použité na vloženie prvkov do A na svoje správne pozície, čím dostaneme utriedené pole.

^ TOP

Vizualizácia

Countingsort

^ TOP

Zápis algoritmu

    countingsort(A[], B[], k)
      for i = 1 to k do
         C[i] = 0
         
      for j = 1 to length(A) do
         C[A[j]] = C[A[j]] + 1
         
      for 2 = 1 to k do
         C[i] = C[i] + C[i-1]
    
      for j = 1 to length(A) do
         B[C[A[j]]] = A[j]
         C[A[j]] = C[A[j]] - 1
^ TOP

Vlastnosti algoritmu

Counting sort má časovú zložitosť Theta(n+k), kde n a k sú dĺžky polí A (vstupné pole) a C (pomocné spočítavacie pole). Aby bol algoritmus efektívny, nesmie byť k v porovnaní s n príliš veľké. Ak k je O(n), tak je čas behu algoritmu Theta(n).
Counting sort je stabilný triediaci algoritmus, ale netriedi prvky na mieste.

^ TOP

Experimentovanie

School of Computer Science, Cardiff University, UK
Demonštrácia vlastností counting sortu.
http://users.cs.cf.ac.uk/C.L.Mumford/tristan/CountingSort.html

Computer Science and Engineering Department, Indian Institute of Technology, India
Animácia counting sortu s možnosťou krokovania.
http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/countingSort/countingSort.html

^ TOP