Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |
| statnice:bakalar:b4b33alg [2026/06/06 10:29] – [Mazání] knedl1k | statnice:bakalar:b4b33alg [2026/06/06 17:15] (current) – [Counting Sort] knedl1k |
|---|
| |
| ==== Counting Sort ==== | ==== Counting Sort ==== |
| Nevyužívá porovnávání, ale frekvenční pole. Nejprve spočítáme výskyty všech hodnot, pak je seřadíme podle počtu. Funguje pouze pro celočíselné hodnoty v omezeném rozsahu. | Nevyužívá porovnávání, ale frekvenční pole. Nejdříve určíme maximální hodnotu v poli. Tu použijeme pro inicializaci pomocného pole, které bude mít velikost max + 1. Po té na každý index pomocného pole uložíme počet výskytu jednotlivých hodnot (postupně procházímme původní pole a přičteme 1). Pak kumulativně přičteme ke každé hodnotě hodnotu zprava. Výsledek nám dává počáteční index, odkud začíná číslo. https://www.youtube.com/watch?v=OKd534EWcdk. Funguje pouze pro celočíselné hodnoty v omezeném rozsahu. |
| |
| * Stabilní, velmi rychlý: $O(n + k)$ (k … rozsah hodnot) | * Stabilní, velmi rychlý: $O(n + k)$ (k … rozsah hodnot) |
