Dlaczego Quicksort jest lepszy od innych algorytmów sortowania w praktyce?

308

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(nlogn)O(n2)O(nlogn)

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(nlogn)O(nlogn)

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.

Janoma
źródło
2
Sortowanie metodą sortowania to w najgorszym przypadku, a sortowanie tablicy liczb całkowitych, w których istnieje znane ograniczenie wielkości liczb całkowitych, można wykonać w czasie O ( n ) za pomocą sortowania zliczającego. O(nlogn)O(n)
Carl Mummert,
13
sorting-algorithms.com ma dość dokładne porównanie algorytmów sortowania.
Joe
2
Aktualizacja reklamy 1: Przypuszczam, że możesz mieć rygorystyczną analizę lub realistyczne założenia. Nie widziałem obu. Na przykład większość analiz formalnych liczy tylko porównania.
Raphael
9
To pytanie wygrało ostatni konkurs na programistów.SE !
Raphael
3
Interesujące pytanie. Jakiś czas temu przeprowadziłem kilka testów z losowymi danymi i naiwną implementacją szybkiego sortowania i scalania. Oba algorytmy działały całkiem dobrze dla małych zestawów danych (do 100 000 pozycji), ale po tym sortowanie scalania okazało się znacznie lepsze. Wydaje się to przeczyć ogólnemu założeniu, że szybkie sortowanie jest tak dobre i wciąż nie znalazłem na to wytłumaczenia. Jedynym pomysłem, jaki mogłem wymyślić, jest to, że zwykle termin „szybkie sortowanie” jest używany w przypadku bardziej złożonych algorytmów, takich jak sortowanie intro, oraz że naiwna implementacja szybkiego sortowania z losowym przestawieniem nie jest tak dobra.
Giorgio

Odpowiedzi:

215

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 KnuthaSztuka 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.74n18.74
    • Połączenie: 12.5nln(n)
    • Heapsort: 16nln(n)+0.01n
    • Wkładki: [ źródło ]2.25n2+7.75n3ln(n) Czas działania kilku algorytmów sortowania

    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:
    Czas działania kilku algorytmów sortowania dla 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

    • 2nln(n)13nln(n)
    • 1.44nln(n)8.66nln(n)
    • 14n214n2

    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

Sebastian
źródło
8
Wyniki typu 2. można przekształcić w wyniki typu 1. przez wstawienie stałych zależnych od maszyny. Dlatego twierdzę, że 2. to lepsze podejście.
Raphael
2
@Raphael +1. Przypuszczam, że zakładasz, że zależne od maszyny jest również zależne od implementacji, prawda? Mam na myśli, że szybka maszyna + słaba implementacja prawdopodobnie nie jest zbyt wydajna.
Janoma,
2
@Janoma Przyjąłem, że analizowany algorytm ma być podany w bardzo szczegółowej formie (ponieważ analiza jest szczegółowa), a implementacja powinna być jak największa z listu. Ale tak, wdrożenie również by się przydało.
Raphael
3
W rzeczywistości analiza typu 2 jest gorsza w praktyce. Maszyny w świecie rzeczywistym są tak skomplikowane, że wyników z typu 2 nie można w pełni przełożyć na typ 1. Porównaj to z typem 1: wykreślić eksperymentalne czasy działania zajmuje 5 minut.
Jules
4
@Jules: „wykreślanie eksperymentalnego czasu działania” nie jest typu 1; nie jest to żadna analiza formalna i nie można jej przenieść na inne maszyny. W końcu dlatego przeprowadzamy analizę formalną.
Raphael
78

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

Quicksort jest zwykle szybki

O(n2)

n1O(nlogn)

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

O(nlogn)O(n2)n

O(nlogn)O(nBlog(nB))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(nBlogMB(nB))Mk

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.

nO(logn)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.

Alex ten Brink
źródło
3
Twoja ostatnia uwaga jest szczególnie cenna. Mój kolega obecnie analizuje implementacje Quicksort w różnych dystrybucjach wejściowych. Niektóre z nich rozkładają się na przykład dla wielu duplikatów.
Raphael
4
O(n2)
8
„[T] nie ma za tym teorii, po prostu dzieje się szybciej.” To stwierdzenie jest wysoce niezadowalające z naukowego punktu widzenia. Wyobraź sobie, że Newton mówi: „Motyle latają w górę, jabłka spadają: nie ma za tym teorii, jabłka po prostu spadają”.
David Richerby
2
@Alex ten Brink, co masz na myśli mówiąc „W szczególności algorytm nie uwzględnia pamięci podręcznej ”?
Hibou57
4
@David Richerby, „To stwierdzenie jest wysoce niezadowalające z naukowego punktu widzenia”: może być tylko świadkiem faktu bez udawania, że ​​powinniśmy być z niego zadowoleni. Niektóre rodziny algorytmów cierpią na brak pełnej formalizacji; Funkcje mieszające są przykładem.
Hibou57
45

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.

Dai
źródło
17
@Raphael Mówiąc krótko: Timsort jest sortowaniem scalającym dla asymptotyków oraz sortowaniem wstawiania dla krótkich danych wejściowych oraz pewną heurystyką, aby skutecznie radzić sobie z danymi, które mają sporadycznie już posortowaną serię (co zdarza się często w praktyce). Dai: oprócz algorytmu list.sortkorzysta z wbudowanej funkcji zoptymalizowanej przez profesjonalistów. Bardziej sprawiedliwe porównanie zapewniłoby wszystkie funkcje napisane w tym samym języku przy takim samym wysiłku.
Gilles
1
@Dai: Mógłbyś przynajmniej opisać przy pomocy jakiego rodzaju danych wejściowych (lub ich dystrybucji), w jakich okolicznościach (mała pamięć RAM, czy jedna implementacja była równoległa, ...) uzyskałeś swoje wyniki.
Raphael
7
Testowaliśmy na liście liczb losowych i częściowo posortowaliśmy, całkowicie posortowaliśmy i posortowaliśmy odwrotnie. To był wstępny kurs pierwszego roku, więc nie było to głębokie badanie empiryczne. Ale fakt, że jest teraz oficjalnie używany do sortowania tablic w Javie SE 7 i na platformie Android, coś znaczy.
Dai,
3
Omówiono to także tutaj: cstheory.stackexchange.com/a/927/74
Jukka Suomela
34

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.

svick
źródło
5
To dyskusyjne wyjaśnienie: scalesort jest również przyjazny dla pamięci podręcznej.
Dmytro Korduban,
2
Myślę, że ta odpowiedź jest w zasadzie poprawna, ale oto kilka szczegółów youtube.com/watch?v=aMnn0Jq0J-E
rgrig
3
prawdopodobnie stała multiplikatywna dla średniej złożoności czasowego sortowania w trybie szybkiego sortowania jest również lepsza (niezależnie od wspomnianego współczynnika pamięci podręcznej).
Kaveh
1
Wspomniany punkt nie jest tak ważny w porównaniu z innymi dobrymi właściwościami szybkiego sortowania.
MMS
1
@Kaveh: „stała multiplikatywna dla średniej złożoności szybkiego sortowania w czasie sprawy jest również lepsza” Czy masz na ten temat jakieś dane?
Giorgio
29

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

O(nlogn)

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.

k10

Raphael
źródło
20

O(nlgn)

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ż:

Kaveh
źródło
3
@Janoma to kwestia używanego języka i kompilatora. Prawie wszystkie języki funkcjonalne (ML, Lisp, Haskell) mogą dokonywać optymalizacji, które zapobiegają wzrostowi stosu, a inteligentniejsze kompilatory dla języków imperatywnych mogą zrobić to samo (GCC, G ++ i uważam, że MSVC to wszystko robi). Godnym uwagi wyjątkiem jest Java, która nigdy nie przeprowadzi tej optymalizacji, więc w Javie sensowne jest przepisywanie rekurencji jako iteracji.
Rafe Kettler
4
@JD, nie można używać optymalizacji połączeń ogonowych z Quicksort (przynajmniej nie do końca), ponieważ wywołuje się dwukrotnie. Możesz zoptymalizować drugie połączenie, ale nie pierwsze.
sick
1
@Janoma, tak naprawdę nie potrzebujesz rekurencyjnej implementacji. Na przykład, jeśli spojrzysz na implementację funkcji qsort w C, nie używa ona wywołań rekurencyjnych, a zatem implementacja staje się znacznie szybsza.
Kaveh,
1
Heapsort jest również na miejscu, dlaczego QS często jest szybszy?
Kevin
6
23240
16

Θ(n2)Θ(nlogn)

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.

0x0
źródło
1
Ale co sprawia, że ​​stałe są tak małe?
sick
1
@svick Ponieważ są one posortowane, in-placetzn. nie jest wymagana dodatkowa pamięć.
0x0
Θ(nlgn)
15

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

Erwan Legrand
źródło
Widziałem coś podobnego do tego, ponieważ zdarzało się, że ciągle dodawaliśmy / próbowaliśmy wstawiać do partii już posortowanych danych. Możesz obejść to średnio, używając losowego szybkiego sortowania (i zaskocz się rzadkim i losowo strasznie powolnym sortowaniem), lub możesz tolerować zawsze wolniejsze sortowanie, które nigdy nie zajmuje zaskakująco dużo czasu. Czasami potrzebujesz także stabilności sortowania. Java przeszła z używania sortowania korespondencji seryjnej na wariant szybkiego sortowania.
Rob
@Rob To nie jest dokładne. Java do dziś używa wariantu scalesort (Timsort). Używa również wariantu quicksort (dual-pivot quicksort).
Erwan Legrand
14

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.

MMS
źródło
3
Czy widziałeś zaawansowane, iteracyjne implementacje Quicksort? Jest wiele rzeczy, ale nie „łatwych”.
Raphael
2
Numer 2 w ogóle nie odpowiada na moje pytanie, a numery 1 i 3 wymagają, moim zdaniem, odpowiedniego uzasadnienia.
Janoma
@Raphael: Są łatwe. Znacznie łatwiej jest zaimplementować szybkie sortowanie w miejscu za pomocą tablicy zamiast wskaźników. I nie musi być iteracyjny, aby być na miejscu.
MMS
Tablice do łączenia nie są takie złe. Po przeniesieniu jednego elementu ze stosu źródłowego na stos docelowy nie musi już tam być. Jeśli korzystasz z tablic dynamicznych, podczas łączenia występuje stały narzut pamięci.
Oskar Skog
@ 1 Mergesort może być również na miejscu. @ 2 Co określa efektywność? Lubię sortowanie po scaleniu, ponieważ moim zdaniem jest to bardzo proste, a jednocześnie wydajne. @ 3 Nieistotne przy sortowaniu dużych ilości danych i wymaga wydajnego wdrożenia algorytmu.
Oskar Skog
11

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

Θ(log(n)2)Θ(nlog(n)2)

Θ(nk)Θ(nm)k=2#number_of_Possible_valuesm=#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.

Θ(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)

Θ(n)Θ(n2)Θ(nlog(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.

Θ(log(n))Θ(n)Θ(n)Θ(log(n))Θ(n2)Θ(n)Θ(n)Θ(log(n))Θ(nlog(n))

Θ(nlog(n))

Wskazówki dotyczące implementacji Quicksort:

Θ(n)Θ(log(n))Θ(nlogk(k1))

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.

Θ(k)Θ(log(k))Θ(1)Θ(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

Θ(log(n))Θ(n)

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

Franki
źródło
(5): Implementacja sortowania Apple sprawdza jeden przebieg w porządku rosnącym lub malejącym zarówno na początku, jak i na końcu tablicy. Jest to bardzo szybkie, jeśli nie ma wielu takich elementów, i może obsłużyć te elementy bardzo skutecznie, jeśli jest ich więcej niż n / ln n. Połącz dwa posortowane tablice i posortuj wynik, a otrzymasz scalenie
gnasher729
8

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.

ab

paproć 0
źródło
5
Twój argument na temat sortowania w trybie Quicksort vs. Quicksort zaczyna się od dużego ruchu, a następnie wykonuje coraz mniejsze ruchy (o około połowę większe na każdym kroku). Sortowanie scalające rozpoczyna się od małego ruchu, a następnie wykonuje coraz większe ruchy (około dwa razy większe na każdym kroku). Nie oznacza to, że jedno jest bardziej wydajne od drugiego.
Gilles