Counting sort

Counting sort je algoritmus řazení, který je efektivní při řazení pole obsahujícího velké skupiny opakujících se prvků. Předpokládá, že všechny prvky pole jsou celá čísla od 1 do k, a běží v konstantním čase. Nevýhodou je potřeba dodatečné paměti pro ukládání četností prvku.

Pomocné pole pro ukládání četnosti

Counting sort potřebuje pro svoji práci pomocné pole prvků seřazených podle velikosti od 1 do k, do kterého ke každému prvku ukládá jeho četnost.

Algoritmus

Algoritmus nejprve zleva či zprava projde vstupní pole a pro každý prvek, na který narazí, zvýší v pomocném poli četnost vyskytu tohoto prvku o 1. Poté, co má v pomocném poli zaznamenán počet výskytů, poupraví toto pole nasledujícím způsobem: ke každé položce přičte počet výskytů všech předchozích položek. Tím u každé položky v pomocném poli získá přesnou pozici hranice, na které bude v seřazeném poli. Následuje vlastní řazení. Algoritmus začne zprava procházet neseřazené pole a pro každý prvek, na který narazí, se podívá do pomocného pole na horní hranici pro umístění. Na tuto hranici ho umístí a zároveň ji sníží o jedna. Takto postupuje, až projde celé pole. Tím je řazení skončeno.

Příklad:
Pole: [1][4][2][4][1][3][1]

Pomocné pole:
1 - 3x
2 - 1x
3 - 1x
4 - 2x

Přepočet na hranice prvku:
1 - 3
2 - 4
3 - 5
4 - 7

Pro první prvek:
[][][1][][][][]
Pomocné pole:
1 - 2
2 - 4
3 - 5
4 - 7
Další kroky(analogicky):
[ ][ ][1][ ][3][ ][ ]
[ ][1][1][ ][3][ ][ ]
[ ][1][1][ ][3][ ][4]
[ ][1][1][2][3][ ][4]
[ ][1][1][2][3][4][4]
[1][1][1][2][3][4][4] - seřazené pole