Counting sort

Counting sort je jeden z efektivních algoritmů řazeni. Nevyhodou je pořeba dodatečné paměti pro ukládání četností prvku. Algoritmus nejprve zleva či zprava projde vstupní pole a pro každy 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ícim zpusobem: ke každe položce přičte počet výskytů všech předchozích položek. Tím u každe položky v pomocném poli získá přesnou pozici hranice,na které se 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ý narazi se podívá do pomocného pole na horní hranici pro umístění a na tuto hranici ho umistí a zaroveň ji sníží o jedna. Takto postupuje až projde cele pole. Tim 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 prvni prvek:
[][][1][][][][]
Pomocné pole:
1 - 2
2 - 4
3 - 5
4 - 7
Další kroky(analogicky):
[ ][ ][1][ ][3][ ][ ]
[ ][ ][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