NOVINKA - Online rekvalifikační kurz Python programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
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í.
Avatar
Jakub Lásko[Saarix]
Tvůrce
Avatar
Jakub Lásko[Saarix]:28.7.2014 9:27

Zdravím všechny, tentokrát se chci podělit o jeden velice pěkný řadící algoritmus, který teď používám.

Jmenuje se: Counting sort
A zde na něj najdete pěkný návod jak ho udělat http://www.algoritmy.net/…ounting-sort

Sám sem byl dost překvapen když dosahuji při řazení 800 000 prvků rychlosti 0,04s. Kdo používá u více prvků stále bubble sort nebo quick sort, tak tady by se rozhodně vyplatilo měnit ;)

Snad ho někdo z vás taky uplatní.

Odpovědět
28.7.2014 9:27
Časem je vše možné.
Avatar
sadlomaslox25
Člen
Avatar
sadlomaslox25:28.7.2014 13:07

vypada hezky, akorat podle me cokoli, co je rychljsi jak O(n log n), coz je quick sort, si to vynahrazuje silenyma pametovima narokama (viz tady tento algoritmus) :D
takze pozor na pamet ;)

 
Nahoru Odpovědět
28.7.2014 13:07
Avatar
coells
Tvůrce
Avatar
Odpovídá na sadlomaslox25
coells:28.7.2014 13:14

Žádný algoritmus založený na porovnávání prvků nemůže být asymptoticky rychlejší než O(n log n). Counting sort ovšem není založený na porovnávání a jako další algoritmy tak může dosahovat až lineární složitosti. Není pravidlem, že by k tomu bylo potřeba extrémní paměti.

 
Nahoru Odpovědět
28.7.2014 13:14
Avatar
sadlomaslox25
Člen
Avatar
sadlomaslox25:28.7.2014 13:27

tak zrovna u toho Counting sortu je ta pametova narocnost silena viz radek kodu:
// vytvorime pole do ktereho budeme pocitat
int[] counts = new int[max - min + 1];

coz podle me znamena ze kdyz budu mit pole o 3 prvcich (500 000 000, 1,2) tak na serazeni techto 3 cisel potrebuje algoritmus cca 2GB :D

nvm jak moc korektne je provedena ta implementace na tech strankach, ale to uz bych radsi pouzil RadixSort (http://www.alg.webzdarma.cz/…5/radix.html) s O(k*N) a pametovou slozitosti O(k+N).

 
Nahoru Odpovědět
28.7.2014 13:27
Avatar
coells
Tvůrce
Avatar
Odpovídá na sadlomaslox25
coells:28.7.2014 13:43

Proto se také counting sort používá pouze v případě, že abs(min-max) << n.

 
Nahoru Odpovědět
28.7.2014 13:43
Avatar
Jakub Lásko[Saarix]
Tvůrce
Avatar
Odpovídá na sadlomaslox25
Jakub Lásko[Saarix]:28.7.2014 14:06

Ten Radix nevypadá špatně, ale jak říkám ten Counting Sort využívám při řazení více prvků v C# a zatím paměťové problémy nebyly a rychlost parádní.

Nahoru Odpovědět
28.7.2014 14:06
Časem je vše možné.
Avatar
Jakub Lásko[Saarix]
Tvůrce
Avatar
Jakub Lásko[Saarix]:28.7.2014 14:08

Pokud hodnoty v poli jsou třeba 0 - 2500 a máš tam 2 000 000 záznamů, tak je to s paměťí v klidu a rychlost je 0.1s ;)

Nahoru Odpovědět
28.7.2014 14:08
Časem je vše možné.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 7 zpráv z 7.