W dniu 2012-10-13 22:53, M.M. pisze:
> 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

Wydaje mi sie, żę fir ma na myśli sortowanieprzez zliczanie
(countingsort), jest szcególnym przypadkiem sortowania
pozycyjnego (radix sort).
Przechodzisz raz tablicę, zliczasz, ile masz jakich wartości
(for... h[ tab[i] ]++; h[n] to ilość elementow w tam o wartości n),
następnie przebiegasz drugi raz i ustawiasz, bo wiesz, którą
wartość gdzie wstawić.

Kubełkowe działa nieco inaczej. Dzielisz zakres danych
na przedziały, każdemu przedziałowi odpowiada kontener.
Przelatujesz tablicę, wrzucasz do odpowiedniego kontenera.
Sortujesz wewnątrz kontenerów i gotowe.

Wszytko to standardowe algorytmy, więc wątpię:


>> 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?

Wątpię, by była to prawda.

W szczególności dlatego, że komisja podczas większości
takich konkursów (PA, olimpiada informatyczna, dolnośląskie
zespolowe cośtam cośtam) nie zagląda do kodu. Liczą się wyniki
na danych testowych.

To może i ja rzucę anegdotę. Olimpiada informatyczna (etap okręgowy)
jakieś 10 lat temu. Jedno z zadanek było dość koszmarne.
Coś z grafami, mało istotne.
Nikt go nie zrobił, gdy nam pokazali, jak, to trwało to godzinę,
mimo braku kawałka implementacji;)
Ale jedna osoba dostała ze wstępnych testów parę punktów. Więc
proszą, aby pokazała. Chłopak zaczyna się wykręcać.
-Ale ja tak tylko taką heurystykę zastosowałem, nie warto...
W końcu namówiony przyznał się.
Zwracał logartym (liczby węzłów) + 1;)

Ale punktów za testy, które program przechodził, nikt mu nie odbierał.


pzdr
bartekltg