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

^{To jest odpowiedź na pytanie do cs.SE autorstwa Janomy . Pełne kredyty i łupy dla niego lub cs.SE.}

W standardowym kursie z algorytmów uczymy się, że quicksort wynosi średnio O (n log n) i O (n²) 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.

Po szybkim spojrzeniu na kilka dłuższych czasów pracy jest naturalne stwierdzenie, ż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).

Nie zgodziłbym się, że quicksort jest lepszy niż inne algorytmy sortowania w praktyce.

Do większości celów Timsort - hybryda między sortowaniem scalania / wstawiania, który wykorzystuje fakt, że sortowane dane często zaczynają się prawie posortowane lub posortowane odwrotnie.

Najprostszy Quicksort (bez losowego obrotu) traktuje ten potencjalnie powszechny przypadek jako O (N ^ 2) (redukując do O (Nlg N) z losowymi obrotami), podczas gdy TimSort może obsłużyć te przypadki w O (N).

Zgodnie z tymi testami porównawczymi w języku C # porównującymi wbudowany quicksort z TimSort, Timsort jest znacznie szybszy w najczęściej posortowanych przypadkach i nieco szybszy w przypadkowym przypadku danych, a TimSort staje się lepszy, jeśli funkcja porównywania jest szczególnie wolna. Nie powtórzyłem tych testów i nie zdziwiłbym się, gdyby Quicksort lekko pobił TimSort za jakąś kombinację losowych danych lub jeśli jest coś dziwnego we wbudowanym sortowaniu C # (opartym na Quicksort), który to spowalnia. Jednak TimSort ma wyraźne zalety, gdy dane mogą być częściowo posortowane, i jest mniej więcej równy szybkiemu sortowaniu pod względem prędkości, gdy dane nie są częściowo posortowane.

TimSort ma również dodatkową zaletę bycia stabilnym gatunkiem, w przeciwieństwie do Quicksort. Jedyną wadą TimSort jest użycie pamięci O (N) w porównaniu z pamięcią O (lg N) w zwykłej (szybkiej) implementacji.

Szybkie sortowanie uważa się za szybsze, ponieważ współczynnik jest mniejszy niż jakikolwiek inny znany algorytm. Nie ma na to żadnego powodu ani dowodu, po prostu nie znaleziono algorytmu o mniejszym współczynniku. To prawda, że ​​inne algorytmy również mają czas O ( n log n ), ale w świecie rzeczywistym współczynnik jest również ważny.

Zauważ, że w przypadku małych wstawiania danych sortowanie (takie, które jest uważane za O ( n ² )) jest szybsze ze względu na naturę funkcji matematycznych. Zależy to od konkretnych współczynników, które różnią się w zależności od maszyny. (Na końcu tak naprawdę działa tylko asembler.) Tak więc czasami hybryda szybkiego sortowania i sortowania wstawiania jest najszybsza w praktyce.

Quicksort nie przewyższa wszystkich innych algorytmów sortowania. Na przykład sortowanie od dołu do góry ( Wegener 2002 ) przewyższa szybkie sortowanie dla rozsądnych ilości danych i jest również algorytmem na miejscu. Jest również łatwy do wdrożenia (przynajmniej nie trudniejszy niż jakiś zoptymalizowany wariant Quicksort).

Po prostu nie jest tak dobrze znany i nie ma go w wielu podręcznikach, co może wyjaśniać, dlaczego nie jest tak popularny jak Quicksort.

Nie powinieneś koncentrować się tylko na najgorszym przypadku i tylko na złożoności czasu. Chodzi bardziej o średnią niż najgorsze, a także o czas i przestrzeń.

Szybkie sortowanie:

• ma średni czas złożoności Θ ( n log n );
• może być zaimplementowany ze złożonością przestrzeni of (log n );

Weź również pod uwagę, że duża notacja O nie uwzględnia żadnych stałych, ale w praktyce robi różnicę, jeśli algorytm jest kilka razy szybszy. Θ ( n log n ) oznacza, że ​​algorytm wykonuje się w K  n  log ( n ), gdzie K jest stałe. Quicksort jest algorytm sortowania porównanie z najniższym K .

Quicksort jest często dobrym wyborem, ponieważ jest dość szybki, względnie szybki i łatwy do wdrożenia.

Jeśli poważnie myślisz o bardzo szybkim sortowaniu dużych ilości danych, prawdopodobnie lepiej jest z pewną odmianą MergeSort. Można to zrobić, aby skorzystać z pamięci zewnętrznej, może korzystać z wielu wątków, a nawet procesów, ale nie są one trywialne w kodzie.

Rzeczywista wydajność algorytmów zależy od platformy, a także języka, kompilatora, uwagi programisty na szczegółach implementacji, konkretnego wysiłku optymalizacyjnego itp. Tak więc „stała przewaga czynnikowa” szybkiego sortowania nie jest zbyt dobrze zdefiniowana - jest to subiektywna ocena oparta na obecnie dostępnych narzędziach i przybliżona ocena „równoważnego wysiłku wdrożeniowego” przez każdego, kto faktycznie wykonuje porównawcze badanie wydajności. .

To powiedziawszy, uważam, że Quicksort działa dobrze (w przypadku losowego wprowadzania danych), ponieważ jest prosty i ponieważ jego struktura rekurencyjna jest stosunkowo przyjazna dla pamięci podręcznej. Z drugiej strony, ponieważ jego najgorszy przypadek jest łatwy do uruchomienia, wszelkie praktyczne zastosowanie szybkiego sortowania będzie musiało być bardziej złożone, niż wskazywałby jego opis w podręczniku: w ten sposób zmodyfikowane wersje, takie jak introsort.

Z biegiem czasu, wraz ze zmianą dominującej platformy, różne algorytmy mogą zyskać lub utracić (źle zdefiniowaną) względną przewagę. Konwencjonalna wiedza na temat względnej wydajności może pozostawać w tyle za tą zmianą, więc jeśli naprawdę nie masz pewności, który algorytm jest najlepszy dla twojej aplikacji, powinieneś wdrożyć oba i przetestować je.