Dnia Sun, 15 Jul 2012 08:47:54 +0000, PK napisal:

> On 2012-07-15, Edek Pienkowski <e...@g...com> wrote:
>> Była mowa o sortowaniu. Czy aby na pewno nie da się żyć bez znajomości
>> quick sorta? Ile razy w życiu trzeba algorytm sortowania napisać
[...]
>
> Quicksort jest dobrym przykładem, bo ma słaby wariant pesymistyczny
> O(n^2). To dyskwalifikuje go w wielu zastosowaniach. Poza tym jest
> niestabilny.

W to akurat nie wątpię, że quicksort dobrym przykładem jest, tylko
jakoś mi umknęło, czego konkretnie miałby być podstawą.

>
> Akurat w przypadku Pythona sytuacja jest niezła, bo zastosowano
> świetnego Timsorta, który ma tylko jedną istotną wadę - "ramożerność".
> Ja zależnie od sytuacji wybieram Timsort lub insertion sort
> (2 skrajnie różne algorytmy, dobrze się uzupełniają).

Czy używa tego algorytmu czy innego, tak na codzień albo nie
zwracam uwagi bo nie muszę, albo kiedy muszę to czytam opis,
bo nigdy nie pamiętam, która biblioteka ma którą wersję,
i czasem muszę też sprawdzić jak się konkretnie metoda nazywa.

Zazwyczaj jestem świadomy sytuacji, kiedy powinienem się na tym
pochylić, a jak się pomylę to profiler szybko mnie naprostuje;
stabilność to osobna cecha, jak o niej nie myślę to zazwyczaj
nie ma ku temu powodu.

> Quicksorta napisałem kilka razy w życiu, bo IMO nadaje się tylko do
> testowania - wtedy korzystam po prostu z tego, co jest w bibliotekach,
> bo zazwyczaj jest lepsze :).

Tu jest cała śmieszność sytuacji: kazano kiedyś w ramach testu
porządnym programistom napisać, już nie pamiętam, chyba binary
search w pół godziny, ale na kartce, bez testów.
Poprawną odpowiedź wypluło z 10% testowanych, reszta w czymś się
sypnęła, przy czym 100% twierdziło, że ma algorytm w małym
palcu, bo to takie oczywiste. Najczęściej któryś warunek
brzegowy nie był poprawnie uwzględniony.

Przyznam się, że u mnie z podstawowych algorytmów rb-tree i
właśnie quicksort mają od X lat status "kiedyś poświęcę
te 10 minut". Zawsze mogę powiedzieć że to wina prowadzących
zajęcia, co najwyżej wspomnieli o rb-tree.

Edek