Dnia Sun, 15 Jul 2012 16:41:06 +0000, PK napisal:

> On 2012-07-15, Edek Pienkowski <e...@g...com> wrote:
>> Sortowanie nie jest z ostatnich 10 lat. Nie wiem, co masz na myśli
>
> Wspomniany wcześniej Timsoft jest z 2002 roku. Nie jest to algorytm
> znany, ale jest bardzo często używany (przez popularność Pythona, więc
> w pewnym sensie ważny :)). Z tego samego roku pochodzi bardzo ciekawy
> spreadsort (polecam poczytać).

Z kwietnia czy października? To już prawie 10 ;)

> Z bardziej znanych... tu nie mam pewności, ale chyba bucket sort
> (jako uogólnienie kilku innych) jest dosyć świeży. Z całą pewnością
> w ostatnich latach ten algorytm był mocno rozwijany.
>
>> mówiąc "algorytmika". Jeżeli tworzenie nowego algorytmu sortowania to ok,
>> ale przy zwykłym stosowaniu i to "często i gęsto" sortowania nie ma
>> żadnego znaczenia, jakiego sorta używa biblioteka, o ile a) nie jest
>> w ciasnej pętli, albo b) nie ma zauważalnie dużo elementów. Ostatecznie
>> i tak z profilerem się nie dyskutuje.
>
> Może w Twoim doświadczeniu nie ma, ale ludzie mają różne sytuacje.
> Np. dla mnie zazwyczaj wariant pesymistyczny jest znacznie bardziej
> istotny niż średni - dlatego m.in. nie używam quicksorta. Poza tym
> często cierpię na deficyt RAMu i staram się dobierać algorytmy in situ.

Ja faktycznie mam takie podejście do sortowania jak do nowego modelu
uchwytu śrubokręta. Zwracam na nie uwagę tylko wtedy gdy jest mi
potrzebny akurat taki a nie inny. Domyślam się, że mamy tu swoistą
symetrię.

> Niektóre algorytmy dobrze radzą sobie z ciągami zupełnie losowymi,
> a inne z już częściowo posortowanymi.

To jest odwieczny problem, dane o określonej skrukturze mogą trafić
w wariant pesymistyczny albo nawet trafiać bardzo często. Brak
struktury to też pewna cecha z gatunku cech strukturalnych,
nie ma jak tego skompresować chociażby.

Z ciekawości, który algorytm najlepiej odwróci sortowanie?
(Poza reverse(), nie wiemy, że są posortowane odwrotnie).

> I to nie jest tak, że chcę być fajny i optymalizuję sortowanie
> 200 numerów telefonów w książce adresowej :). Te problemy są dla mnie
> naprawdę istotne :).

Rozumiem. O większości powyższych słyszałem, w dokumentacji bibliotek
Pythona też pamiętam, że chyba faktycznie był to timsort, ale mój
mózg nisko spriorytetyzował tę informację i się zagubiła.

Zaskoczyło mnie, że te algorytmy są stosunkowo nowe. Doczytam kiedyś
w wolnej chwili, kiedyś ta wiedza się może przydać. Kolejna dziedzina,
gdzie wydawałoby się że nic już nowego nie powstanie, a jednak.

> Wiem, że jestem w tym wypadku marginesem, ale to nie zmienia faktu, że
> każda osoba używająca jakiejś funkcji "sort()" powinna przynajmniej
> wiedzieć, co ta funkcja zwraca, czyli czy algorytm jest stabilny.
> Widywałem już programy sypiące się, bo autor o tym zapomniał.

Prawda, ja też widzę często bardziej podstawowe błędu typu a < b < c
i c < a. Nie różnię się tutaj od innych programistów, robię błędy
które muszę poprawiać, takie też z podobną częstotliwością jak
if (a) zamiast if (!a).

Edek