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

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

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 :).

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ł.

pozdrawiam,
PK