W standardowym kursie z algorytmów uczymy się, że quicksort wynosi średnio a O ( n 2 ) w najgorszym przypadku. Jednocześnie badane są inne algorytmy sortowania, które w najgorszym przypadku to O ( n log n ) (np. Scalesort i heapsort ), a nawet czas liniowy w najlepszym przypadku (np. Bąbelkowy ), ale z pewnymi dodatkowymi potrzebami pamięci.$O(n \log n)$$O(n^2)$$O(n \log n)$

Po szybkim spojrzeniu na dłuższe czasy działania można oczywiście powiedzieć, że Quicksort nie powinien być tak wydajny jak inne.

Weź również pod uwagę, że uczniowie uczą się podczas podstawowych kursów programowania, że ​​rekursja nie jest ogólnie dobra, ponieważ mogłaby zużyć zbyt dużo pamięci itp. Dlatego (i chociaż nie jest to prawdziwy argument), daje to wyobrażenie, że Quicksort może nie być naprawdę dobrze, ponieważ jest to algorytm rekurencyjny.

Dlaczego zatem Quicksort przewyższa inne algorytmy sortowania w praktyce? Czy ma to związek ze strukturą rzeczywistych danych ? Czy ma to związek ze sposobem działania pamięci w komputerach? Wiem, że niektóre wspomnienia są znacznie szybsze od innych, ale nie wiem, czy to jest prawdziwy powód tego sprzecznego z intuicją działania (w porównaniu z teoretycznymi szacunkami).

Aktualizacja 1: kanoniczna odpowiedź mówi, że stałe zaangażowane w średniego przypadku są mniejsze niż stałe zaangażowane w inne algorytmy O ( n log n ) . Jednak nie widziałem jeszcze właściwego uzasadnienia tego, z dokładnymi obliczeniami zamiast tylko intuicyjnych pomysłów.$O(n\log n)$$O(n\log n)$

W każdym razie wydaje się, że występuje prawdziwa różnica, jak sugerują niektóre odpowiedzi, na poziomie pamięci, gdzie implementacje wykorzystują wewnętrzną strukturę komputerów, wykorzystując na przykład, że pamięć podręczna jest szybsza niż pamięć RAM. Dyskusja jest już ciekawe, ale jeszcze bym chciał zobaczyć więcej szczegółów w odniesieniu do zarządzania pamięcią, ponieważ wydaje się, że odpowiedź ma z nim zrobić.

Aktualizacja 2: Istnieje kilka stron internetowych oferujących porównanie algorytmów sortowania, niektóre z nich są bardziej wyszukane niż inne (w szczególności sorting-algorithms.com ). Takie podejście, poza przedstawieniem ładnej pomocy wizualnej, nie odpowiada na moje pytanie.

Krótka odpowiedź

Argument wydajności bufora został już szczegółowo wyjaśniony. Ponadto istnieje nieodłączny argument, dlaczego Quicksort jest szybki. Jeśli zostaną zaimplementowane tak jak w przypadku dwóch „skrzyżowań wskaźników”, np. Tutaj , wewnętrzne pętle mają bardzo małe ciało. Ponieważ jest to najczęściej wykonywany kod, to się opłaca.

Długa odpowiedź

Po pierwsze,

Przeciętnego przypadku nie istnieje!

Ponieważ najlepsze i najgorsze przypadki często są skrajnościami rzadko występującymi w praktyce, przeprowadzana jest średnia analiza przypadków. Ale każda średnia analiza przypadków zakłada pewien rozkład danych wejściowych ! Do sortowania typowym wyborem jest model losowej permutacji (domyślnie przyjęty na Wikipedii).

Dlaczego Notacja?$O$

Odrzucanie stałych w analizie algorytmów odbywa się z jednego głównego powodu: jeśli interesują mnie dokładne czasy działania, potrzebuję (względnych) kosztów wszystkich zaangażowanych podstawowych operacji (nawet wciąż ignorując problemy z buforowaniem, potokowanie w nowoczesnych procesorach ...). Analiza matematyczna może policzyć, jak często wykonywana jest każda instrukcja, ale czasy wykonywania pojedynczych instrukcji zależą od szczegółów procesora, np. Czy 32-bitowe mnożenie liczb całkowitych zajmuje tyle samo czasu, co dodanie.

Istnieją dwa wyjścia:

1. Napraw jakiś model maszyny.

   Odbywa się to w książkowej serii Dona Knutha „ Sztuka programowania komputerowego” na sztuczny „typowy” komputer wynaleziony przez autora. W tomie 3 znajdziesz dokładne średnie wyniki przypadków dla wielu algorytmów sortowania, np

   • Quicksort: $11.667(n+1)\ln(n)-1.74n-18.74$
   • Połączenie: $12.5 n \ln(n)$
   • Heapsort: $16 n \ln(n) +0.01n$
   • Wkładki: ^{[ źródło ]}$2.25n^2+7.75n-3ln(n)$
     

   Te wyniki wskazują, że Quicksort jest najszybszy. Ale zostało to udowodnione tylko na sztucznej maszynie Knutha, niekoniecznie oznacza to, powiedzmy, twój komputer x86. Należy również zauważyć, że algorytmy odnoszą się inaczej do małych danych wejściowych:
   
   ^{[ źródło ]}

2. Analizuj abstrakcyjne podstawowe operacje .

   W przypadku sortowania opartego na porównaniu zwykle są to wymiany i kluczowe porównania . W książkach Roberta Sedgewicka, np. „Algorytmach” , takie podejście jest stosowane. Znajdziesz tam

   • $2n\ln(n)$$\frac13n\ln(n)$
   • $1.44n\ln(n)$$8.66n\ln(n)$
   • $\frac14n^2$$\frac14n^2$

   Jak widać, nie pozwala to na porównanie algorytmów jako dokładnej analizy środowiska wykonawczego, ale wyniki są niezależne od szczegółów maszyny.

Inne rozkłady wejściowe

Jak wspomniano powyżej, średnie przypadki są zawsze w odniesieniu do niektórych rozkładów wejściowych, więc można rozważyć inne niż przypadkowe permutacje. Np. Przeprowadzono badania dla Quicksort z równymi elementami i jest ładny artykuł na temat standardowej funkcji sortowania w Javie

Istnieje wiele punktów, które można postawić odnośnie tego pytania.

Quicksort jest zwykle szybki

$O(n^2)$

$n-1$$O(n \log n)$

Quicksort jest zwykle szybszy niż większość rodzajów

$O(n \log n)$$O(n^2)$$n$

$O(n \log n)$$O(\frac{n}{B} \log (\frac{n}{B}))$$B$

Powodem tej wydajności pamięci podręcznej jest to, że liniowo skanuje dane wejściowe i liniowo dzieli je na partycje. Oznacza to, że możemy w pełni wykorzystać każde ładowanie pamięci podręcznej, jakie wykonujemy, odczytując każdą liczbę ładowaną do pamięci podręcznej przed zamianą pamięci podręcznej na inną. W szczególności algorytm nie uwzględnia pamięci podręcznej, co zapewnia dobrą wydajność pamięci podręcznej na każdym poziomie pamięci podręcznej, co jest kolejną wygraną.

$O(\frac{n}{B} \log_{\frac{M}{B}} (\frac{n}{B}))$$M$$k$

Quicksort jest zwykle szybszy niż Mergesort

To porównanie dotyczy całkowicie stałych czynników (jeśli weźmiemy pod uwagę typowy przypadek). W szczególności należy wybrać między nieoptymalnym wyborem osi obrotu dla Quicksort a kopią całego wejścia dla Mergesort (lub złożonością algorytmu potrzebnego do uniknięcia tego kopiowania). Okazuje się, że ten pierwszy jest bardziej wydajny: nie kryje się za tym żadna teoria, po prostu dzieje się szybciej.

$n$$O(\log n)$$O(n)$

Na koniec zauważ, że Quicksort jest nieco wrażliwy na dane wejściowe, które zdarzają się w odpowiedniej kolejności, w którym to przypadku może pominąć niektóre swapy. Mergesort nie ma takich optymalizacji, co sprawia, że ​​Quicksort jest nieco szybszy w porównaniu do Mergesort.

Użyj rodzaju, który odpowiada Twoim potrzebom

Podsumowując: żaden algorytm sortowania nie jest zawsze optymalny. Wybierz ten, który odpowiada Twoim potrzebom. Jeśli potrzebujesz algorytmu, który jest najszybszy w większości przypadków, i nie przeszkadza ci, że może być nieco powolny w rzadkich przypadkach i nie potrzebujesz stabilnego rodzaju, użyj Quicksort. W przeciwnym razie użyj algorytmu, który lepiej odpowiada Twoim potrzebom.

W jednym z samouczków programowania na moim uniwersytecie poprosiliśmy studentów, aby porównali wydajność szybkiego sortowania, scalania, sortowania wstawiania w porównaniu z wbudowaną list.sort Pythona (zwaną Timsort ). Wyniki eksperymentów zaskoczyły mnie głęboko, ponieważ wbudowana lista.sort działała o wiele lepiej niż inne algorytmy sortowania, nawet w przypadkach, które łatwo powodowały awarię szybkiego sortowania i łączenia. Dlatego przedwczesne jest stwierdzenie, że zwykła implementacja Quicksort jest najlepsza w praktyce. Ale jestem pewien, że istnieje o wiele lepsza implementacja quicksort lub jego hybrydowa wersja.

To miły artykuł na blogu autorstwa Davida R. MacIvera wyjaśniający Timsort jako formę adaptacyjnego połączenia.

Myślę, że jednym z głównych powodów, dla których QuickSort jest tak szybki w porównaniu z innymi algorytmami sortowania, jest to, że jest przyjazny dla pamięci podręcznej. Kiedy QS przetwarza segment tablicy, uzyskuje dostęp do elementów na początku i na końcu segmentu i przesuwa się w kierunku środka segmentu.

Kiedy zaczynasz, uzyskujesz dostęp do pierwszego elementu w tablicy, a pamięć („lokalizacja”) jest ładowana do pamięci podręcznej. A kiedy próbujesz uzyskać dostęp do drugiego elementu, (najprawdopodobniej) jest już w pamięci podręcznej, więc jest bardzo szybki.

Inne algorytmy, takie jak heapsort, nie działają w ten sposób, często wskakują do tablicy, co czyni je wolniejszymi.

Inni powiedzieli już, że asymptotyczny średni czas działania Quicksort jest lepszy (na stałe) niż w przypadku innych algorytmów sortowania (w niektórych ustawieniach).

$\cal{O}(n \log n)$

Zauważ, że istnieje wiele wariantów Quicksort (patrz np. Rozprawa Sedgewicka). Działają inaczej w różnych dystrybucjach wejściowych (jednolite, prawie posortowane, prawie odwrotnie posortowane, wiele duplikatów, ...), a inne algorytmy mogą być lepsze dla niektórych.

$k \approx 10$

$O(n \lg n)$

ps: ściślej mówiąc, bycie lepszym od innych algorytmów zależy od zadania. W przypadku niektórych zadań lepszym rozwiązaniem może być zastosowanie innych algorytmów sortowania.

Zobacz też:

• Porównanie szybkiego sortowania z innymi algorytmami sortowania

• Porównanie sortowania sterty z innymi algorytmami sortowania

$\Theta(n^2)$$\Theta(n\log n)$

Drugim powodem jest to, że wykonuje in-placesortowanie i działa bardzo dobrze w środowiskach pamięci wirtualnej.

AKTUALIZACJA:: (Po komentarzach Janomy i Svicka)

Aby to lepiej zilustrować, pozwólcie, że podam przykład przy użyciu sortowania scalającego (myślę, że sortowanie scalające jest kolejnym szeroko przyjętym algorytmem sortowania po szybkim sortowaniu) i powiem wam, skąd pochodzą dodatkowe stałe (według mojej najlepszej wiedzy i dlaczego myślę, że Szybkie sortowanie jest lepsze):

Rozważ następującą sekwencję:

12,30,21,8,6,9,1,7. The merge sort algorithm works as follows:

(a) 12,30,21,8    6,9,1,7  //divide stage
(b) 12,30   21,8   6,9   1,7   //divide stage
(c) 12   30   21   8   6   9   1   7   //Final divide stage
(d) 12,30   8,21   6,9   1,7   //Merge Stage
(e) 8,12,21,30   .....     // Analyze this stage

Jeśli zależy ci w pełni zobaczyć, jak przebiega ostatni etap, pierwsze 12 jest porównywane z 8, a 8 jest mniejsze, więc idzie pierwsze. Teraz 12 jest PONOWNIE w porównaniu z 21, a 12 idzie dalej i tak dalej, i tak dalej. Jeśli weźmiesz ostateczne scalenie, tj. 4 elementy z 4 innymi elementami, spowoduje to wiele porównań DODATKOWYCH jako stałe, które NIE są uwzględniane w Szybkim sortowaniu. To jest powód, dla którego preferowane jest szybkie sortowanie.

Moje doświadczenie w pracy z danymi ze świata rzeczywistego jest takie, że Quicksort to zły wybór . Quicksort działa dobrze z danymi losowymi, ale dane ze świata rzeczywistego najczęściej nie są losowe.

W 2008 roku wyśledziłem wiszący błąd oprogramowania do użycia quicksort. Chwilę później napisałem proste implantacje sortowania przez wstawianie, sortowania szybkiego, sortowania i scalania sortowania i testowałem je. Moje sortowanie scalające przewyższyło wszystkie pozostałe podczas pracy na dużych zestawach danych.

Od tego czasu sortowanie metodą scalania jest moim wybranym algorytmem sortowania. To jest eleganckie. Jest prosty do wdrożenia. Jest to stabilny rodzaj. Nie ulega degeneracji do zachowania kwadratowego, jak robi to Quicksort. Przełączam na sortowanie wstawiane, aby posortować małe tablice.

Przy wielu okazjach zastanawiałem się, czy dana implementacja działa zaskakująco dobrze w przypadku szybkiego sortowania, ale okazało się, że tak naprawdę nie jest to szybki przegląd. Czasami implementacja przełącza się między Quicksort a innym algorytmem, a czasami w ogóle nie używa Quicksort. Na przykład funkcje qsort () GLibc'a faktycznie używają sortowania według scalania. Tylko w przypadku niepowodzenia przydzielenia przestrzeni roboczej wraca do szybkiego sortowania w miejscu, które komentarz kodu nazywa „wolniejszym algorytmem” .

Edycja: Języki programowania, takie jak Java, Python i Perl, również używają sortowania scalającego, a ściślej pochodnej, takiej jak Timsort lub sortowania scalającego dla dużych zestawów i sortowania wstawiania dla małych zestawów. (Java używa również podwójnego szybkiego przestawiania, który jest szybszy niż zwykły szybki).

1 - Szybkie sortowanie jest na miejscu (nie wymaga dodatkowej pamięci, innej niż stała ilość).

2 - Szybkie sortowanie jest łatwiejsze do wdrożenia niż inne wydajne algorytmy sortowania.

3 - Szybkie sortowanie ma mniejsze stałe czynniki w czasie działania niż inne wydajne algorytmy sortowania.

Aktualizacja: W celu sortowania w trybie scalania należy wykonać pewne „scalanie”, które wymaga dodatkowych tablic do przechowywania danych przed scaleniem; ale w szybkim sortowaniu nie. Dlatego szybkie sortowanie jest na miejscu. Istnieją również dodatkowe porównania dla scalania, które zwiększają stałe czynniki w rodzaju scalania.

W jakich warunkach konkretny algorytm sortowania jest rzeczywiście najszybszy?

$\Theta(\log(n)^2)$$\Theta(n \cdot \log(n)^2)$

$\Theta(n \cdot k)$$\Theta(n \cdot m)$$k=2^{\#number\_of\_Possible\_values}$$m = \#maximum\_length\_of\_keys$

3) Czy podstawowa struktura danych składa się z powiązanych elementów? Tak -> zawsze używaj w miejscu sortowania korespondencji seryjnej. Istnieją zarówno łatwe do wdrożenia stałe wielkości, jak i adaptacyjne (czyli naturalne) oddolne miejsca, łączące różnego rodzaju arie dla połączonych struktur danych, a ponieważ nigdy nie wymagają kopiowania całych danych na każdym etapie i nigdy nie wymagają rekurencji, są one szybciej niż jakikolwiek inny rodzaj sortowania opartego na porównaniach, nawet szybciej niż szybkie sortowanie.

$\Theta(n)$

5) Czy wielkość podstawowych danych może być powiązana z małą do średniej? np. czy n <10 000 ... 100 000 000 (w zależności od podstawowej architektury i struktury danych)? Tak -> użyj sortowania bitonicznego lub połączenia parzystego nieparzystego Batchera. Idź 1)

$\Theta(n)$$\Theta(n^2)$$\Theta(n \cdot \log(n)^2)$najgorszy przypadek jest znany, a może spróbuj sortować grzebieniem. Nie jestem pewien, czy sortowanie skorupowe czy grzebieniowe będzie w praktyce całkiem dobre.

$\Theta(\log(n))$$\Theta(n)$$\Theta(n)$$\Theta(\log(n))$$\Theta(n^2)$$\Theta(n)$$\Theta(n)$$\Theta(\log(n))$$\Theta(n \cdot \log(n))$

$\Theta(n \cdot \log(n))$

Wskazówki dotyczące implementacji Quicksort:

$\Theta(n)$$\Theta(\log(n))$$\Theta(n^{\log_k(k-1)})$

2) Istnieją oddolne, iteracyjne warianty Quicksort, ale AFAIK, mają one takie same asymptotyczne granice przestrzeni i czasu, jak odgórne, z dodatkowymi wadami trudnymi do wdrożenia (np. Jawne zarządzanie kolejką). Z mojego doświadczenia wynika, że ​​ze względów praktycznych nie warto ich brać pod uwagę.

Wskazówki dotyczące implementacji połączenia

1) połączenie typu „z dołu do góry” jest zawsze szybsze niż połączenie typu z góry na dół, ponieważ nie wymaga żadnych wywołań rekurencyjnych.

2) bardzo naiwny tryb scalania można przyspieszyć, stosując podwójny bufor i przełączając bufor zamiast kopiować dane z tablicy czasowej po każdym kroku.

3) W przypadku wielu rzeczywistych danych adaptacyjny scalanie jest znacznie szybszy niż scalanie o stałym rozmiarze.

$\Theta(k)$$\Theta(\log(k))$$\Theta(1)$$\Theta(n)$

Z tego, co napisałem, jasne jest, że Quicksort często nie jest najszybszym algorytmem, chyba że spełnione są wszystkie poniższe warunki:

1) istnieje więcej niż „kilka” możliwych wartości

2) podstawowa struktura danych nie jest powiązana

3) nie potrzebujemy stabilnego zamówienia

4) dane są na tyle duże, że uruchamia się nieznacznie nieoptymalny asymptotyczny czas działania sortera bitonicznego lub kombinacji parzystych parzystych nieparzystych

5) dane nie są prawie posortowane i nie składają się z większych już posortowanych części

6) możemy uzyskać dostęp do sekwencji danych jednocześnie z wielu miejsc

$\Theta(\log(n))$$\Theta(n)$

ps: Ktoś musi mi pomóc w formatowaniu tekstu.

Większość metod sortowania musi przenosić dane w krótkich krokach (na przykład scalanie sortuj wprowadza zmiany lokalnie, a następnie łączy ten niewielki kawałek danych, a następnie łączy większy ...). W rezultacie potrzebujesz wielu ruchów danych, jeśli dane są daleko od miejsca docelowego.

$a \le b$