Avatar
Jakub Lásko[Saarix]:

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:

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
Redaktor
Avatar
Odpovídá na sadlomaslox25
coells:

Žá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:

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
Redaktor
Avatar
Odpovídá na sadlomaslox25
coells:

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
Odpovídá na sadlomaslox25
Jakub Lásko[Saarix]:

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]:

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.