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ć

W większości rzeczywistych problemów oczywiście jest to obojętne.
Ale sporo zależy od sytuacji. Np. dla mnie sortowanie jest często
niezłym wyzwaniem i wymaga chwili koncentracji. Każdy programista może
się znaleźć w takiej sytuacji, więc warto znać nie tyle same algorytmy,
co ich charakterystykę - wiedzieć jakiego użyć w danym problemie. Po kod
zawsze można zerknąć do jakiejś publikacji lub po prostu na wiki :).

Quicksort jest dobrym przykładem, bo ma słaby wariant pesymistyczny
O(n^2). To dyskwalifikuje go w wielu zastosowaniach. Poza tym jest
niestabilny.

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

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

pozdrawiam,
PK