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?
źródło
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!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:
źródło
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.
źródło
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 ...
źródło