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
Došiel 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ť iba tento kurz
Získaj okamžitý prístup ku kurzu bez
časového obmedzenia.
50 kreditov
Obsah článku spadá pod licenciu Premium, kúpou článku súhlasíš so zmluvnými podmienkami.
- Prístup k jednotlivým lekciám podľa spôsobu obstarania.
- 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.