Triedenie Counting sort

Toto triedenie tvorí algoritmus, ktorý nepoužíva porovnávanie.

Dá sa použiť len v prípade, ak chceme zoradiť celé čísla. Tieto celé čísla sa použijú ako index pomocného poľa. V jazykoch, kde indexom poľa môže byť aj niečo iné ako číslo, by sa dalo použiť napríklad aj na zotrieďovanie písmen.

Ak teda máme vstupné pole s 1000 číslami od 1 do 100, pomocné pole bude veľkosti 100 – pre každú z možných hodnôt bude k dispozícii jedna bunka poľa. Budeme si v ňom pamätať počty výskytov každej z hodnôt. Na jeden prechod vstupným poľom (rýchlosť O(n) ) zvýšime vždy hodnotu tej bunky v pomocnom poli, ktorá je na pozícii rovnej hodnote vo vstupnom poli. Potom na jeden prechod pomocným poľom vyrobíme výsledný výstup – O(n) (Pomocné pole má síce len 100 prvkov, ale na každom prvku vykonáme toľko operácií výpisu, koľko bol príslušný súčet. Vlastne spolu vykonáme 1000 operácií výpisu)

Tento algoritmus je výhodný, len ak počet rôznych hodnôt nie je príliš veľký.  Ak by sme mali 1000 čísel, pričom hodnoty môžu byť od 1 do milión, pomocné pole by muselo byť veľkosti milión. Takéto triedene by bolo náročnejšie jednak na pamäť, a dvak na počet operácii pri výpise výstupného poľa, pretože by sme museli cyklom prechádzať celé miliónprvkové pole (hoci by aj na väčšine miest boli nuly).

Counting sort

Pridaj komentár

Vaša e-mailová adresa nebude zverejnená. Vyžadované polia sú označené *