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ícím způsobem: ke každe 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é 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ý narazí, se podívá do pomocného pole na horní hranici pro umístění. Na tuto hranici ho umístí a zaroveň ji sníží o jedna. Takto postupuje, až projde cele 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 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