Counting sort

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 prvků, nabývajících jen malý počet různých diskrétních hodnot.

Předpoklady

Abychom mohli využít toto řazení, je třeba aby:

• Počet různých hodnot prvků (M) 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 výskytu 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, dokud neprojde 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é pole, které se třídí, není potřeba mít v paměti, proto se tento algoritmus dá použít i na pole, která jsou tak velká, že se nemohou do paměti celá vejít.

Příklad

V příkladu ukážeme, jak setřídit čísel 1, 4, 2, 4, 1, 3, 1.

Pomocné pole (číslo - počet výskytů):

1 - 3x
2 - 1x
3 - 1x
4 - 2x

Přepočet na hranice prvku (číslo - index konce pole)

1 - 3
2 - 4
3 - 5
4 - 7

V prvním kroce máme umístit číslo 1. Protože víme, že číslo jedna má 3 výskyty, umístíme jej na 3. pozici a snížíme v pomocném poli počet zbývajících výskytů na 2.
[ ][ ][1][ ][ ][ ][ ]

Pomocné pole po prvním kroku

1 - 2
2 - 4
3 - 5
4 - 7

Další kroky probíhají analogicky, zde je uvedeno, jak se bude postupně plnit seřazené pole:

[ ][ ][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 a algoritmus končí

Odkazy

Externí odkazy

• řazení v HTML5
• řazení pomocí Java appletu
• implementace v jazyku java