Dlaczego Quicksort nazywa się „Quicksort”?

Celem tego pytania nie jest dyskusja na temat zalet tego algorytmu w stosunku do jakiegokolwiek innego algorytmu sortowania - z pewnością jest wiele innych pytań, które to robią. To pytanie dotyczy nazwy. Dlaczego Quicksort nazywa się „Quicksort”? Jasne, przez większość czasu jest „szybki”, ale nie zawsze. Możliwość degeneracji do O (N ^ 2) jest dobrze znana. Istnieją różne modyfikacje Quicksort, które łagodzą ten problem, ale te, które sprowadzają najgorszy przypadek do gwarantowanego O (n log n), na ogół nie są już nazywane Quicksort. (np. Introsort).

Zastanawiam się tylko, dlaczego spośród wszystkich dobrze znanych algorytmów sortowania, jest to jedyna zasługująca na nazwę „szybka”, która opisuje nie tak, jak algorytm działa, ale jak szybko (zwykle) jest. Mergesort nazywa się tak, ponieważ łączy dane. Heapsort nazywa się tak, ponieważ używa sterty. Introsort bierze swoją nazwę od „introspekcji”, ponieważ monitoruje własną wydajność, aby zdecydować, kiedy zmienić z Quicksort na Heapsort. Podobnie dla wszystkich wolniejszych - Bubblesort, Sortowanie wstawiania, Sortowanie wyboru itp. Wszystkie są nazwane tak, jak działają. Jedynym innym wyjątkiem, jaki mogę wymyślić, jest „Bogosort”, który jest tak naprawdę tylko żartem, którego nikt tak naprawdę nie stosuje w praktyce. Dlaczego Quicksort nie nazywa czegoś bardziej opisowego, na przykład „Sortowanie partycji” lub „Sortowanie przestawne”, które opisują to, co faktycznie robi? To nawet nie jest przypadek „dotarłem tu pierwszy”. Mergesort został opracowany 15 lat przed Quicksort. (Odpowiednio 1945 i 1960 według Wikipedii)

Wydaje mi się, że jest to raczej pytanie historyczne niż programowe. Jestem ciekawy, jak to się nazywa - czy to był dobry marketing?

— Darrel Hoffman
źródło

Timsort, który jest ulepszonym Quicksortem, nie bierze nazwy po tym, jak działa, ale raczej od swojego wynalazcy. Nazwy takie jak flashsort lub sortowanie introspektywne nie powiedzieć zbyt wiele o algorytm albo.

— vartec

What's in a name? that which we call a rose By any other name would smell as sweet;To lub być tak samo szybkie. Poza tym możliwość zdegenerowania do O (N ^ 2) ma niewielką szansę, że się wydarzy, a N LogN jest całkiem dobry jak na algorytm, mimo że mamy dziś szybsze algorytmy. Poza tym, zanim pojawiło się coś szybszego, było już za późno, wszyscy już nazywali to Quicksort!

— Ampt

@vartec Timsort pochodzi z Mergesort, a nie z Quicksort, ale zgodzę się, to kolejny wyjątek. Introsort nie daje ci całego algorytmu, ale przynajmniej opisuje coś, jak on działa - jest „introspektywny”. Flashsort Nie jestem zbyt dobrze zaznajomiony, ale myślę, że nazywa się tak, ponieważ „flashuje” każdy element, aby zgadnąć, gdzie powinien być?

— Darrel Hoffman

@Apt W rzeczywistości, w najbardziej podstawowej formie Quicksort, przypadek O (N ^ 2) jest całkiem prawdopodobny w typowym przypadku, w którym dane są już posortowane lub prawie takie. Trzeba przyznać, że późniejsze zmiany, takie jak Mediana of-3 lub losowy element przestawny, sprawiają, że jest on znacznie rzadszy, ale nazwa ta jest nadal używana w przypadku implementacji, w których brakuje takich ulepszeń.

— Darrel Hoffman

Najwyraźniej jest lepszy niż najszybszy?

— JeffO

Odpowiedzi:

W 1962 r. Badania nad algorytmami sortowania nie były tak zaawansowane, jak dzisiaj, a informatyk Tony Hoare znalazł nowy algorytm, który był szybszy od drugiego, dlatego opublikował artykuł o nazwie Quicksort i jak cytowano, tytuł pozostał.

Cytując streszczenie:

Podano opis nowej metody sortowania w sklepie o swobodnym dostępie na komputerze. Metoda ta bardzo dobrze wypada w porównaniu z innymi znanymi metodami prędkości, oszczędności pamięci i łatwości programowania. Pewne udoskonalenia metody, które mogą być przydatne w optymalizacji wewnętrznych pętli, opisano w drugiej części artykułu.

— Johnnes
źródło

Przypis na stronie 11 w dołączonym pliku PDF sugeruje, że wcześniejszy artykuł na temat Quicksort został opublikowany w 1961 r. Artykuł ten jest również wspomniany w części Odniesienia na końcu artykułu.

— FrustratedWithFormsDesigner

1961, Algorythm 64: Quicksort

— Pieter B

Wydaje mi się, że jest to tak blisko prawidłowej odpowiedzi, jak to tylko możliwe. Wyjaśnia, kto go nazwał, ale nie dlaczego wciąż używa tej nazwy, skoro istnieją nowsze i potencjalnie szybsze alternatywy. Dobra lektura - ciekawe jest zobaczyć, jak wiele rzeczy z lat 60. wciąż dotyczy współczesnej technologii.

— Darrel Hoffman

@DarrelHoffman Dlaczego nazwa miałaby się zmieniać? W którym momencie wady wywołania algorytmu Quicksort przeważałyby nad kosztem próby nakłonienia wszystkich do nazywania go PartitionSort lub cokolwiek innego?

— prosfilaes

Wierzę, że pierwotnie nazywał się Hoare Sort od nazwiska wynalazcy, ale nazwa zmieniła się dość wcześnie, ponieważ Hoare brzmiał trochę zbyt blisko dziwki po angielsku. Co do tego, dlaczego wybrali „szybki” zamiast czegoś innego, nie jestem pewien.

— Evicatos
źródło

-1

Wierzę, że dzieje się tak, ponieważ w momencie jego wynalezienia było ono znacznie szybsze niż wszystkie (a raczej większość, ponieważ szybkość zależy również w dużym stopniu od rodzaju danych, a w niektórych przypadkach inny algorytm staje się znacznie szybszy niż szybkie sortowanie) algorytmy tam.

Tak, to jest historyczne (nie znam jednak dokładnie tej historii ...)

Ale zgadzam się, że zamiast tego jego nazwa powinna zawierać wskazówkę dotyczącą algorytmu ...

— Olivier Dulac
źródło