Counting sort

Tento článek potřebuje úpravy.

Můžete Wikipedii pomoci tím, že ho vylepšíte. Jak by měly články vypadat, popisují stránky Vzhled a styl, Encyklopedický styl a Odkazy.

Tento článek není dostatečně ozdrojován a může tedy obsahovat informace, které je třeba ověřit.
Jste-li s popisovaným předmětem seznámeni, pomozte doložit uvedená tvrzení doplněním referencí na věrohodné zdroje.

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