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 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íš se smluvní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.
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.