Counting sort
Ako sme sa dozvedeli v článku Dolnej odhad zložitosti problému triedenia, nemôžeme triediť s lepšou časovou zložitosťou, než O (n log n). Tento limit súvisí s rozhodovacím stromom, ktorý musíme vzájomným porovnávaním prvkov pokryť. Ale čo keby sme mohli triediť tak, bez toho aby sme prvky medzi sebou porovnávali? Mohli by sme potom zotrieďiť poľa v lineárnom čase? Znie to šialene, ale je to úplne možné. Na tomto princípe je založených hneď niekoľko triediacich algoritmov, jedným z nich je aj Counting sort.
Algoritmus triedi iba celé čísla, čo nemusí byť problém, pretože v drvivej väčšine prípadov triedime celé čísla a vo zvyšku prípadov väčšinou môžeme objekty na celé čísla previesť (napr. Čísla s 2 desatinnými miestami prenásobiť stomi, zotrieďiť a potom znovu vydeliť). Triedi na princípe pomocného poľa, ktorému sa hovorí sčítací pole, niekedy tiež indexovacie poľa. To bude dlhé tak
...koniec náhľadu článku...
Pokračuj ďalej
Minul si až sem a to je super! Veríme, že ti prvé lekcie ukázali niečo nového a užitočného.
Chceš v kurze pokračovať? Prejdi do prémiové sekcie.
Kúpiť tento kurz
Obsah článku spadá pod licenciu Premium, kúpou článku súhlasíš so zmluvnými podmienkami.
- Neobmedzený a trvalý prístup k jednotlivým lekciím.
- Kvalitné znalosti v oblasti IT.
- Zručnosti, ktoré ti pomôžu získať vysnívanú a dobre platenú prácu.
Popis článku
Požadovaný článok má nasledujúci obsah:
Counting sort - Ukážka algoritmu counting sort, ktorý zoradí čísla podľa veľkosti v lineárnom čase. Zdrojové kódy pre jazky Java, C #, Delphi, Ruby.
Kredity získaš, keď podporíš našu sieť. To môžeš urobiť buď zaslaním symbolickej sumy na podporu prevádzky alebo pridaním obsahu na sieť.
David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.