Počítání třídění
Počítání třídění| Související problém | Algoritmus řazení |
|---|---|
| Datová struktura | Prkno |
| Nejhorší případ |
|---|
| Nejhorší případ |
|---|
Počítání sort ( počítání sort v angličtině), nazývaný také třídění bin , je třídění algoritmus počítáním, která se aplikuje na celočíselné hodnoty .
Definice
Princip je založen na konstrukci histogramu dat, poté na skenování tohoto ve stále větší míře, aby se rekonstruovala seřazená data. Pojem stability zde nedává smysl, protože histogram ovlivňuje data - několik identických prvků bude představováno jedním kvantovaným prvkem. Toto třídění proto nelze použít na složité struktury a je vhodné výhradně pro data skládající se z celých čísel mezi známou min. Hranicí a známou max. Hranicí . Z důvodu účinnosti musí být relativně blízko u sebe a počet prvků musí být relativně velký.
V této konfiguraci a s distribucí dat podle diskrétního jednotného zákona je toto třídění nejrychlejší (jeden obchoduje, svým způsobem, výpočetní čas proti paměti). Velmi konkrétní omezení uložené na jeho vstupní hodnoty z něj dělá lineární časové třídění , zatímco optimální porovnání vyžaduje řadu operací v řádu .
Příklad
Předpokládáme, že máme záložku pole složenou ze 100 celých čísel mezi 0 a 30 (včetně limitů). Způsob třídění počítáním je následující: spočítáme počet „0“, počet „1“, ..., počet „30“ přítomných na kartě a kartu rekonstruujeme přidáním hodnot podle jejich vzrůstajícího množství (netřídí se hodnoty, ale počítání těchto hodnot v tabulce).
Pole 5 celých čísel 1, 27, 3, 1, 3 obsahuje 2krát 1, 2krát 3 a 1krát 27, pole seřazené podle metody řazení je tedy: 1, 1, 3, 3, 27.
Tabulka před a po třídění:
| X | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| karta [x] | 1 | 27 | 3 | 1 | 3 |
| karta [x] tříděna | 1 | 1 | 3 | 3 | 27 |
Počítací tabulka:
| X | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| arrCount [x] | 0 | 2 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Algoritmus
Algoritmus zde uvedený není jediným řešením problému a nemusí být optimální. Uvažuje se, že index tabulky začíná na 0. Znaménko =se používá pro přiřazení. Pole tabje pole, které se má seřadit, a předává se jako parametr funkce triParComptage. Proměnná borneSuperieure, je maximální celočíselná hodnota přítomná v tab.
Funkce triParComptagepoužívá mezilehlé proměnné:
- tabComptage, je pole obsahující n prvků, kde n je maximální hodnota v tab.
- ia jjsou celočíselné proměnné, které se používají k procházení polí taba tabComptage.