Lekce 8 - Counting sort
V minulé lekci, Dolní odhad složitosti problému třídění, jsme si ukázali dolní odhad složitosti problému třídění.
Jak jsme se dozvěděli v článku Dolní odhad složitosti problému třídění, nemůžeme třídit s lepší časovou složitostí, než O(n log n). Tento limit souvisí s rozhodovacím stromem, který musíme vzájemným porovnáváním prvků pokrýt. Ale co kdybychom mohli třídit tak, aniž bychom prvky mezi sebou porovnávali? Mohli bychom potom setřídit pole v lineárním čase? Zní to šíleně, ale je to naprosto možné. Na tomto principu je založených hned několik třídících algoritmů, jedním z nich je i Counting sort.
Algoritmus třídí pouze celá čísla, což nemusí být problém, protože v drtivé většině případů třídíme celá čísla a ve zbytku případů většinou můžeme objekty na celá čísla převést (např. čísla s 2 desetinnými místy pronásobit stem, setřídit a poté znovu vydělit). Třídí na principu pomocného pole, kterému se říká sčítací pole, někdy také indexovací pole. To bude dlouhé tak
...konec náhledu článku...
Pokračuj dál
Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.
roční PŘEDPLATNÉ
1 082 Kč
měsíčně, placeno ročně (12 984 Kč)14 000+ lekcí, cvičení a testů
6 000+ ti zůstane napořád
Neomezený přístup ke všem aktuálním
i připravovaným kurzům.
Koupit pouze tento kurz
Získej okamžitý přístup ke kurzu bez
časového omezení.
50 Kč
Obsah článku spadá pod licenci Premium, koupí článku souhlasíš s Provozními podmínkami.
- Přístup k jednotlivým lekcím dle způsobu pořízení.
- Kvalitní znalosti v oblasti IT.
- Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.
Popis článku
Požadovaný článek má následující obsah:
Counting sort - Ukázka algoritmu counting sort, který seřadí čísla podle velikosti v lineárním čase. Zdrojové kódy pro jazky Java, C#, Delphi, Ruby.
David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.