W dniu 2012-10-14 22:57, kenobi pisze:
> W dniu niedziela, 14 października 2012 22:51:46 UTC+2 użytkownik kenobi napisał:
>> ...użytkownik kenobi napisał:


>>> co tu robi to --h ? jest na pewno dobrze?

Na pewno jest dobrze.

W h trzymasz liczbę wystąpień.

Pod h[0] masz liczbę zer, pod h[1] liczbę jedynek

Robisz sumy częściowe
teraz pod h[0] nadal masz liczbę zer,
ale pod h[1] liczbę zer i jedynek. pod h[2] liczbe zer,
jedynek i dwójek.

Ta na co pokazuje temp[ h[2] ] ?
pokazuje na pierwsze miejsce _po_ ostatniej dwójce.
Czyli ostatnia dwójka powinna znaleśc się na miejscu
o jeden wcześniej.
Robimy --h[2], pod wynikiem wkłądamy co trzeba.

h pełni rolę _ruchomych_ wskaźników pokazujących,
gdzie układać daną liczbę.

Ok, przyznaje, nie jest to wersja edukacyjna,
i zawiera trochę 'chackierskich przedwczesnych
optymalizacji' i skrótowe konstrukcje.
Dopiero co się nimi zachwysałeś

być może
temp[--h[(unsigned short)tab[j]]]=tab[j];
->
kategoria = (unsigned short)tab[j];
--h[kategoria]; //przesuwamy wskażnik tablicy dla elementow kategorii
kategoria
indeks = h[kategoria];
temp[indeks] = tab[j]

byłaby czytelniejsza;)


>> nie rozumiem tego zlozenia, jak sortowanie tego
>>
>> co bylo posortowane po niskiej polowie po wysokiej czesci zlozy sie tak by
wszystko bylo ok?

_Sortowanie stabilne_. Jeśli w drugim sortowaniu dwa elementy są takie
same, to ich względna kolejność pozostanie taka sama jak po pierwszym.

> w kazdym razie jesli to nie ma bledu i dziala

Nie ma, działa.

> to jest to sprytny kawalek kodu - dziwne jednak jakoby to mialo byc tylko 2-3 razy
szybsze,

Bo tu przelatujemy po dużej tablicy 6 razy, a w qsorcie
log(N) razy. Log2(10^7) = 23 (tak naprawdę mniej, bo
końcówkę robi się inaczej, a do tego działa się bardziej
'lokalnie', co jest szybsze).

Dopiero co się szkicem tego algorytmu zachwycałeś.
Od szkicu do implementacji droga wiedzie przez
nieraz upierdliwe szczegóły;)

Drzewa AVL są w idei super. Ale weź na szybko zaimplementuj
równoważenie.

> new mona wyrzucic i zrobic histogramy na statycznych tablicach

Statyczna tablica na 40MB?

To nie jest nawet zły pomysł. To głupi pomysł.

Zrobiłem wersję z dodatkowym parametrem, buforem tworzonym
raz na zewnątrz (poza licznikiem czasu) i przekazywanym do środka.
Różnice były zbyt małe by warto było o nich wspominać,
więc nawet nie pisałem.

pzdr
bartekltg