Counting sort

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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. Algoritmus řadí stabilně.

Předpoklady[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Časová náročnost[editovat | editovat zdroj]

Č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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]