Counting sort

Z Wikipedie, otevřené encyklopedie
Jump to navigation Jump to search

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ů a počtu různých prvků (O(N+M)), 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říděné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]