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.
Koupit tento kurz
Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.
- Neomezený a trvalý přístup k jednotlivým lekcím.
- 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.
Kredity získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.
David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.