W dniu sobota, 13 października 2012 19:37:28 UTC+2 użytkownik kenobi napisał:
> oczywiscie i tak jest to slamazarstwo
> najlepsze sortowanie to to co ja nazywam
> metoda chrissa kaserskiego, czyli
> h[ tab[i] ]++;
Przepiekna sztuczka, do dzis pamietam uczucie euforii gdy
sie po raz pierwszy dowiedzialem o tej metodzie :) Zdaje sie ze
ta sztuczka nazywa sie sortowaniem kubelkowym. Niestety ma ona
wade. Gdy ilosc roznych wartosci w tab jest duza to potem na
posortoanie h i tak potrzeba M*log(M) operacji (gdzie M to ilosc
roznych wartosci).

> Podobno kiedys zrobil tak na jakiejs
> olimpiadzie jako nastolatek i komisja
> mu tego nie uznala ;-) zarabista anegdota
> (pisalem o tym z rok czy dwa temu)
Moze w tresci zadania byl jakis kruczek?

> Mozna to uogolnic np w h(tab[i])
> robiac galaz drzewa, albo innymi metodami
> i mysle ze to raczej jest po prostu najszybsze
Jesli jest mala ilosc roznych wartosci (innymi slowy
te same wartosci powtarzaja sie czesto) to z pewnoscia
bedzie najszybsze.

W praktyce pewnie przyda sie jeszcze jakias funkcja hash
czestos[ hash(elementy[i]) % size ]++.

Pozdrawiam