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émiovej sekcie.
ročné PREDPLATNÉ
44 €
mesačne, platené ročne (528 €)14 000+ lekcií, cvičení a testov
6 000+ ti zostane navždy
Neobmedzený prístup ku všetkým aktuálnym
aj pripravovaným kurzom.
Kúpiť iba tento kurz
Získaj okamžitý prístup ku kurzu bez
časového obmedzenia.
2 €
Obsah článku spadá pod licenciu Premium, kúpou článku súhlasíš s Prevádzkový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.
David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.