Counting sort
Counting sort je algoritmus řazení, který je vhodný pro řazení velkého pole prkvů nabývajících jen malý diskrétní počet různých hodnot.
Předpoklady
Abychom mohli využít toto řazení, je třeba aby:
- Počet různých hodnot (M) prvků byl významně menší než celkový počet prvků (N).
- Potřebujeme pomocné pole, ve kterém bychom mohli zapisovat a číst hodnotu četnosti v konstantním čase O(1). Tuto podmínku splňuje pole indexované hodnotou nebo hashem hodnoty prvku.
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 následují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.
Asymptotická náročnost
Časová náročnost
Časová náročnost je lineární k počtu prvků (O(N)), protože musíme pro každý prvek zvýšit údaj o četnosti v pomocném poli a pak každý prvek znovu vypsat do výsledného setřízeného pole.
Paměťová náročnost
Paměťová náročnost je (O(M)), protože si potřebujeme pamatovat četnosti pro všechny hodnoty prvků. Celé třízené pole nepotřebujeme mít v paměti, proto se tento algoritmus dá použít i na pole, která jsou tak velká, že se nemohou vejít do paměti.
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