IT rekvalifikace s garancí práce. Seniorní programátoři vydělávají až 160 000 Kč/měsíc a rekvalifikace je prvním krokem. Zjisti, jak na to!
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

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

Znalosti v hodnotě stovek tisíc získáš za pár korun

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

Koupit všechny aktuálně dostupné lekce s funkcí odevzdávání úloh za pouhých 50 Kč
Aktuální stav konta 0 Kč
Koupí tohoto balíčku získáš přístup ke všem 9 článkům (9 lekcí) tohoto kurzu.

Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.

Co od nás v dalších lekcích dostaneš?
  • 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íť.

Článek pro vás napsal David Hartinger
Avatar
David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.
Unicorn university David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity