Quick Sort Vs Merge Sort [duplicate]

Szybkie sortowanie jest zazwyczaj szybsze niż sortowanie scalające, gdy dane są przechowywane w pamięci. Jednak gdy zestaw danych jest ogromny i jest przechowywany na urządzeniach zewnętrznych, takich jak dysk twardy, sortowanie scalanie jest wyraźnym zwycięzcą pod względem prędkości. Minimalizuje kosztowne odczyty zewnętrznego napędu, a także dobrze nadaje się do obliczeń równoległych.

Dla sortowania scalonego najgorsze jest O(n*log(n)), dla sortowania szybkiego: O(n²). W innych przypadkach (avg, best) oba mają O(n*log(n)). Jednak szybkie sortowanie jest stałą spacji, gdzie sortowanie scalające zależy od struktury, którą sortujesz.

Zobacz to porównanie .

Można go również zobaczyć wizualnie.

Osobiście chciałem przetestować różnicę między sortowaniem szybkim i sortowaniem scalonym i zobaczyłem czasy pracy dla próbki 1,000,000 elementów.

Szybkie sortowanie było w stanie to zrobić w 156 milisekund podczas gdy Merge sort zrobił to samo w 247 milisekund

Szybkie sortowanie danych było jednak losowe i szybkie sortowanie działa dobrze, jeśli dane są losowe, gdzie nie jest to przypadek z sortowaniem scalonym, tj. załatwione czy nie. Ale sortowanie scalające wymaga jednego pełnego dodatkowego miejsca, a szybkie sortowanie nie jest sortowaniem na miejscu

Napisałem dla nich obszerny program roboczy, który ilustruje również zdjęcia.

O ile quicksort jest często lepszym Wyborem niż sortowanie scalające, o tyle na pewno są chwile, kiedy sortowanie scalające jest lepszym wyborem. Najbardziej oczywistym czasem jest moment, w którym niezwykle ważne jest, aby algorytm działał szybciej niż O(n^2). Quicksort jest zwykle szybszy od tego, ale biorąc pod uwagę teoretyczne najgorsze możliwe Wejście, Może działać w O (N^2), co jest gorsze od najgorszego możliwego sortowania scalającego.

Quicksort jest również bardziej skomplikowany niż mergesort, zwłaszcza jeśli chcesz napisać naprawdę solidna implementacja, a więc jeśli dążysz do prostoty i łatwości utrzymania, sortowanie scalające staje się obiecującą alternatywą z bardzo małą stratą wydajności.

Oprócz innych: sortowanie scalające jest bardzo wydajne dla niezmiennych struktur danych, takich jak listy połączone, i dlatego jest dobrym wyborem dla (czysto) funkcjonalnych języków programowania.

Źle zaimplementowany quicksort może być zagrożeniem bezpieczeństwa .

Quicksort jest na miejscu. Wystarczy zamienić pozycje danych podczas funkcji partycjonowania. Mergesort wymaga dużo więcej kopiowania danych. Potrzebujesz innego tymczasowego przechowywania (zazwyczaj tego samego rozmiaru co oryginalna tablica danych) dla funkcji scalania.

Quicksort nazywa się tak nie bez powodu,

Highlights : oba rodzaje są stabilne (po prostu uciążliwe dla implementacji ) , więc przejdźmy do złożoności

Jest to bardzo mylące, ponieważ notacje big-oh są rozlane i "nadużywane", obie mają średnią złożoność sprawy wynoszącą 0 (nlogn),

Ale sortowanie merge jest zawsze 0 (nlogn), podczas gdy quicksort dla złych partycji, tj. skośne partycje jak 1 element-10 element (co może się zdarzyć dzięki posortowanej lub odwróconej liście posortowanej ) może prowadzić do 0 (N^2)..

.. i tak mamy randomizowane quicksort, gdzie losowo wybieramy pivot i unikamy takiego przekrzywionego podziału, tym samym unieważniając cały scenariusz N^2 w każdym razie nawet dla umiarkowanie przekrzywionych partycji jak 3-4, mamy nlog (7/4)n, idealnie chcemy 1-1 partion , a więc całe 2 Z O(nlog (2)n).

Więc jest O (nlogn) , prawie zawsze i w przeciwieństwie do sortowania scalającego stałe ukryte pod notacją "big-oh" są lepsze dla quicksort niż dla mergesort ..oraz nie zużywa dodatkowej przestrzeni, takiej jak sortowanie scalające.

Ale uzyskanie quicksort uruchomić idealnie wymaga tweaking, przeformułowanie, quicksort daje możliwości do tweak ....

ODPOWIEDŹ lekko pochyliłaby się w kierunku quicksort w.r. T na zmiany wprowadzone za pomocą DualPivotQuickSort dla prymitywnych wartości . Jest on używany w JAVA 7 do sortowania w java.util.Tablice

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

Implementację JAVA7 znajdziesz tutaj - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Dalsze niesamowite czytanie na DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Nie jest prawdą, że quicksort jest lepszy. Zależy to również od tego, co masz na myśli lepiej, zużycia pamięci lub prędkości.

Pod względem zużycia pamięci, w najgorszym przypadku, ale quicksort może używać pamięci n^2 (tzn. każda partycja jest od 1 do n-1), podczas gdy sortowanie merge używa nlogn.

Powyższe następuje pod względem prędkości.

Quicksort jest na miejscu. Nie potrzebujesz dodatkowej pamięci. Co jest niezwykle ważne.

Dobry wybór mediany sprawia, że jest ona jeszcze bardziej efektywna, ale nawet zły wybór mediany kwarantanny Theta (nlogn).