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í.
Pouze tento týden sleva až 80 % na e-learning týkající se Swiftu. Zároveň využij výhodnou slevovou akci až 30 % zdarma při nákupu e-learningu - více informací.
swift week + discount 30

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.

Omezená nabídka: Nauč se vše a ušetři

Koupit lekce a funkce postupně a po jednom 20 bodů
Koupit všechny aktuálně dostupné lekce s funkcí odevzdávání úloh za exkluzivní cenu 17 bodů (43 Kč)
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 11 lekcím s kontrolou a certifikací a ještě navíc ušetříš 8 Kč. Nabídka je omezená pouze pro první lekce z kurzu a obsahuje exkluzivní slevu 15%.
17 bodů získáš za přidání svého článku na síť nebo odpovídá 50 Kč 43 Kč

Pozor, pokud si koupíš pouze tuto lekci, ztratíš nárok na speciální slevu 15% na balíček všech lekcí.

Koupit jen lekci 10 bodů
Na svém účtu máš aktuálně 0 bodů
10 bodů získáš za přidání svého článku na síť nebo odpovídá 25 Kč

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.

Body 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 Čápka
Avatar
David je zakladatelem ITnetwork a programování se profesionálně věnuje 13 let. Má rád Nirvanu, sushi 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