Dlaczego quicksort jest lepszy niż mergesort?

Jak wiele osób zauważyło, średnia wydajność sprawy dla quicksort jest szybsza niż mergesort. Ale jest to prawdą tylko wtedy, gdy zakładasz stały czas dostępu do dowolnego fragmentu pamięci na żądanie.

W pamięci RAM to założenie nie jest złe (nie zawsze jest prawdziwe z powodu pamięci podręcznej, ale nie jest takie złe). Jeśli jednak twoja struktura danych jest wystarczająco duża, aby żyć na dysku, to quicksort zostanie zabity przez fakt, że twój przeciętny dysk robi coś około 200 losowe poszukiwania na sekundę. Ale ten sam dysk nie ma problemów z odczytem lub zapisem megabajtów na sekundę danych sekwencyjnie. Co dokładnie robi mergesort.

Dlatego, jeśli dane muszą być sortowane na dysku, naprawdę, naprawdę chcesz użyć jakiejś odmiany na mergesort. (Ogólnie można quicksort sublists, a następnie rozpocząć łączenie ich razem powyżej pewnego progu wielkości.)

Ponadto, jeśli musisz zrobić cokolwiek z zestawami danych o tej wielkości, zastanów się, jak uniknąć poszukiwań na dysk. Na przykład dlatego standardowo zaleca się upuszczanie indeksów przed wykonaniem dużych obciążeń danych w bazach danych, a następnie odbudowywanie indeksu później. Utrzymanie indeksu podczas ładowania oznacza ciągłe poszukiwanie dysku. Natomiast jeśli upuścisz indeksy, baza danych może odbudować indeks, najpierw sortując informacje, które mają być rozpatrywane (oczywiście za pomocą mergesort!) , a następnie wczytywanie go do struktury danych BTREE dla indeksu. (BTREEs są naturalnie utrzymywane w porządku, więc ty może załadować jeden z posortowanego zbioru danych z kilkoma poszukiwaniami na dysk.)

Było wiele okazji, w których zrozumienie, jak uniknąć poszukiwań dysków, pozwoliło mi sprawić, że zadania przetwarzania danych zajmują godziny, a nie dni lub tygodnie.

Właściwie, QuickSort to O (n²). Jego średni przypadek to O(nlog (n)), ale jego najgorszy przypadek to O(n²), który występuje, gdy uruchomisz go na liście, która zawiera kilka unikalnych elementów. Randomizacja trwa O (n). Oczywiście nie zmienia to najgorszego przypadku, po prostu uniemożliwia złośliwemu użytkownikowi wykonywanie sortowania przez długi czas.

QuickSort jest bardziej popularny, ponieważ:

1. jest na miejscu (MergeSort wymaga dodatkowej pamięci liniowej do liczba elementów do posortowania).
2. ma małą ukrytą stałą.

Animowane algorytmy sortowania pokazują szereg algorytmów w 4 różnych warunkach początkowych (losowych, prawie posortowanych, odwróconych, niewielu unikalnych) i mogą pomóc.

" a jednak większość ludzi używa Quicksort zamiast Mergesort. Dlaczego?"

Jednym z psychologicznych powodów, które nie zostały podane, jest po prostu to, że Quicksort jest sprytniej nazwany. czyli dobry marketing.

Tak, Quicksort z potrójnym parcjowaniem jest prawdopodobnie jednym z najlepszych algorytmów sortowania ogólnego przeznaczenia, ale nie można zapomnieć o tym, że sortowanie "szybkie" brzmi znacznie potężniej niż sortowanie "Scalanie".

Jak zauważyli inni, najgorszym przypadkiem Quicksort jest O (N^2), podczas gdy mergesort i heapsort pozostają w O(nlogn). W przeciętnym przypadku jednak wszystkie trzy są O (nlogn); więc są dla zdecydowanej większości przypadków porównywalne.

Co sprawia, że Quicksort lepiej średnio jest to, że pętla wewnętrzna implikuje porównanie kilku wartości z jednym, podczas gdy na dwa pozostałe terminy są różne dla każdego porównania. Innymi słowy, Quicksort wykonuje o połowę więcej odczytów niż pozostałe dwa algorytmy. On wydajność nowoczesnych procesorów jest mocno zdominowana przez czasy dostępu, więc w końcu Quicksort staje się doskonałym pierwszym wyborem.

Chciałbym dodać, że z wymienionych do tej pory algorytmów (mergesort, quicksort i heap sort) tylko mergesort jest stabilny. Oznacza to, że kolejność nie zmienia się dla tych wartości, które mają ten sam klucz. W niektórych przypadkach jest to pożądane.

Ale, prawdę mówiąc, w praktycznych sytuacjach większość ludzi potrzebuje tylko dobrej średniej wydajności i quicksort jest... quick =)

Wszystkie algorytmy sortowania mają swoje wzloty i upadki. Zobacz Artykuł Wikipedii dla algorytmów sortowania {[6] } dla dobra przegląd.

Mu! Quicksort nie jest lepszy, dobrze nadaje się do innego rodzaju aplikacji niż mergesort.

Mergesort jest wart rozważenia, jeśli liczy się szybkość, nie można tolerować złej wydajności w najgorszym przypadku, a dostępna jest dodatkowa przestrzeń.1

Stwierdziłeś, że " oboje są O (nlogn) [...]". To jest złe. "Quicksort używa porównań n^2/2 w najgorszym przypadku."1.

Jednak najważniejszą właściwością według moje doświadczenie to łatwa implementacja dostępu sekwencyjnego, którą można wykorzystać podczas sortowania przy użyciu języków programowania z paradygmatem imperatywnym.

1 Sedgewick, Algorytmy

Quicksort jest najszybszym algorytmem sortowania w praktyce, ale ma wiele patologicznych przypadków, które mogą sprawić, że będzie działać tak źle jak O (n2).

Heapsort jest gwarantowany do pracy w O (n*ln (n)) i wymaga tylko skończonej dodatkowej pamięci. Ale jest wiele cytatów z rzeczywistych testów, które pokazują, że heapsort jest znacznie wolniejszy niż quicksort średnio.

From The Wikipedia entry on Quicksort:

Quicksort rywalizuje również z mergesort, kolejny rodzaj rekurencyjny algorytm, ale z korzyścią czas trwania najgorszego przypadku Θ(nlogn). Mergesort jest rodzajem stabilnym, w przeciwieństwie do quicksort i heapsort, i może być łatwo przystosowany do pracy na linked listy i bardzo duże listy przechowywane na wolne nośniki, takie jak dysk storage lub network attached storage. Chociaż quicksort można napisać do działają na linked listy, często będzie cierpią z powodu słabych wyborów pivot bez losowy dostęp. Główną wadą of mergesort jest to, że podczas działania na tablicach wymaga Θ (n) pomocniczego miejsce w najlepszym przypadku, natomiast wariant quicksort z wbudowanym partycjonowanie i rekurencja ogonowa tylko przestrzeń Θ (logn). (Zauważ, że gdy operowanie na listach połączonych, mergesort wymaga tylko niewielkiej, stałej ilości magazynowania pomocniczego.)

Wyjaśnienie Wikipedii brzmi:

Zazwyczaj quicksort jest znacznie szybszy w praktyce niż inne algorytmy Θ (nlogn), ponieważ jego wewnętrzna pętla może być efektywnie zaimplementowana na większości architektur, a w większości rzeczywistych danych możliwe jest dokonywanie wyborów projektowych, które minimalizują prawdopodobieństwo wymaganego czasu kwadratowego.

Quicksort

Mergesort

Myślę, że są też problemy z ilością pamięci potrzebnej do Mergesort (czyli Ω (n)), którego implementacje quicksort nie mają. W najgorszym przypadku są to te same ilości czasu algorytmicznego, ale mergesort wymaga więcej miejsca na dysku.

Quicksort nie jest lepszy niż mergesort. W przypadku O(N^2) (najgorszy przypadek, który rzadko się zdarza), quicksort jest potencjalnie znacznie wolniejszy niż O(nlogn) typu merge. Quicksort ma mniej narzutu, więc z małymi N I wolnymi komputerami jest lepiej. Ale komputery są dziś tak szybkie, że dodatkowy narzut mergesort jest znikomy, a ryzyko bardzo powolnego quicksort znacznie przewyższa nieistotny narzut mergesort w większości przypadków.

DODATKOWO, mergesort pozostawia elementy z identyczne klucze w ich pierwotnej kolejności, przydatny atrybut.

Chciałbym dodać do istniejących wielkich odpowiedzi trochę matematyki o tym, jak QuickSort wykonuje, gdy odbiegają od najlepszego przypadku i jak prawdopodobne jest to, co mam nadzieję pomoże ludziom zrozumieć trochę lepiej, dlaczego przypadek O (n^2) nie jest prawdziwym problemem w bardziej wyrafinowanych implementacjach QuickSort.

Poza przypadkowymi problemami z dostępem, istnieją dwa główne czynniki, które mogą mieć wpływ na wydajność QuickSort i oba są związane z tym, jak pivot porównuje się do danych załatwione.

1) mała liczba kluczy w danych. Zbiór danych o tej samej wartości będzie sortowany w czasie N^2 na 2-partycji waniliowej QuickSort, ponieważ wszystkie wartości z wyjątkiem lokalizacji obrotu są umieszczane po jednej stronie za każdym razem. Współczesne implementacje rozwiązują to za pomocą metod takich jak użycie sortowania 3-partycyjnego. Metody te wykonują się na zbiorze danych o tej samej wartości w czasie O (n). Użycie takiej implementacji oznacza więc, że wejście z niewielką liczbą kluczy faktycznie poprawia czas wykonania i nie jest już problemem.

2) bardzo zły wybór pivot może spowodować najgorszą wydajność. W idealnym przypadku, pivot zawsze będzie taki, że 50% dane są mniejsze i 50% dane są większe, tak, że dane wejściowe będą łamane na pół podczas każdej iteracji. To daje nam N porównań i zamiany razy log-2(N) rekursje dla O (N*logn) czas.

Jak bardzo nieidealny wybór Pivota wpływa na czas realizacji?

Rozważmy przypadek gdzie obrót jest konsekwentnie wybierany w taki sposób, że 75% danych znajduje się po jednej stronie obrotu. Nadal jest O (N * logn), ale teraz podstawa logu zmieniła się na 1/0. 75 lub 1.33. Zależność wydajności przy zmianie bazy jest zawsze stałą reprezentowaną przez log(2) / log(newBase). W tym przypadku stała ta wynosi 2.4. Tak więc ta jakość wyboru Pivota trwa 2,4 razy dłużej niż idealna.

Jak szybko to się pogarsza?

Niezbyt szybko, aż do wyboru Pivota robi się (konsekwentnie) bardzo źle:

• 50% z jednej strony: (idealny przypadek)
• 75% na jednej stronie: 2,4 razy dłużej
• 90% na jednej stronie: 6,6 razy dłuższa
• 95% na jednej stronie: 13,5 razy dłużej
• 99% na jednej stronie: 69 razy dłużej

Gdy zbliżamy się do 100% z jednej strony, część dziennika wykonania zbliża się do n, a cała realizacja asymptotycznie zbliża się do O (n^2).

W naiwnej implementacji QuickSort, przypadki takie jak sortowane array (dla 1st element pivot) lub odwrotne sortowanie tablicy(dla ostatniego elementu pivot) niezawodnie wytworzy najgorszy czas wykonania O (N^2). Dodatkowo, implementacje z przewidywalnym wyborem pivot mogą być poddawane atakom DoS przez dane, które są zaprojektowane tak, aby generować najgorszy przypadek wykonania. Współczesne implementacje unikają tego za pomocą różnych metod, takich jak randomizowanie danych przed sortowaniem, wybór mediany 3 losowo wybranych indeksów itp. Z tą randomizacją w miksie mamy 2 przypadki:

• mały zestaw danych. Najgorszy przypadek jest możliwy, ale O (N^2) nie jest katastrofalny, ponieważ n jest na tyle małe, że n^2 jest również małe.
• duży zestaw danych. Najgorszy przypadek jest możliwy w teorii, ale nie w praktyce.

Jak prawdopodobne jest, że zobaczymy fatalne wyniki?

Szanse są znikają bardzo małe . Rozważmy rodzaj 5000 wartości:

Nasza hipotetyczna implementacja wybierze pivot używając mediany 3 losowo wybrane indeksy. Czopy, które znajdują się w przedziale 25% -75%, uznamy za "dobre", a czopy, które znajdują się w przedziale 0% -25% lub 75% -100% za "złe". Jeśli spojrzeć na rozkład prawdopodobieństwa używając mediany 3 indeksów losowych, każda rekurencja ma szansę 11/16 na zakończenie z dobrym obrotem. Przyjmijmy 2 konserwatywne (i fałszywe) założenia, aby uprościć matematykę:

1. Dobre czopy są zawsze dokładnie przy podziale 25%/75% i działają w idealnym przypadku 2,4*. My nigdy uzyskaj idealny split lub dowolny split lepszy niż 25/75.

2. Złe obroty są zawsze najgorsze i zasadniczo nic nie przyczyniają się do rozwiązania.

Nasza implementacja QuickSort zatrzyma się na n=10 i przełączy się na sortowanie wstawiania, więc potrzebujemy 22 partycji 25%/75% pivot, aby przełamać wejściową wartość 5,000 w dół tak daleko. (10*1.333333^22 > 5000) lub, wymagamy 4990 najgorszych przypadków. Należy pamiętać, że jeśli zgromadzimy 22 dobre pivoty w dowolnym punkcie to sortowanie zakończy się, więc najgorszy przypadek lub cokolwiek w jego pobliżu wymagaekstremalnie pecha. Jeśli potrzeba nam 88 rekurencji, aby faktycznie osiągnąć 22 dobre pivoty wymagane do sortowania do n=10, to byłby to 4 * 2.4 * przypadek idealny lub około 10 razy czas wykonania przypadku idealnego. Jak prawdopodobne jest, że po 88 rekurencjach nie osiągniemy wymaganych 22 dobrych pivotów?

Dwumianowe rozkłady prawdopodobieństwa mogą na to odpowiedzieć, a odpowiedź wynosi około 10^-18. (n 88, k to 21, p to 0.6875) Twój użytkownik jest około tysiąc razy bardziej narażony na uderzenie pioruna w ciągu 1 sekundy, jaką zajmuje kliknięcie [SORT], niż aby zobaczyć, że 5000 sortowania przedmiotów działa gorzej niż 10*idealny przypadek. Szansa ta zmniejsza się wraz ze wzrostem zbioru danych. Oto kilka rozmiarów tablic i odpowiadające im szanse na działanie dłuższe niż 10 * idealne:

• tablica 640 pozycji: 10^-13 (wymaga 15 dobrych punktów na 60 prób)
• tablica 5000 przedmioty: 10^-18 (wymaga 22 dobrych pivotów z 88 prób)
• Array of 40,000 items:10^-23 (requires 29 good pivots out of 116)

Pamiętaj, że jest to z dwoma konserwatywnymi założeniami, które są gorsze od rzeczywistości. Tak więc rzeczywista wydajność jest jeszcze lepsza, a równowaga pozostałego prawdopodobieństwa jest bliższa ideałowi niż nie.

Wreszcie, jak już inni wspomnieli, nawet te absurdalnie nieprawdopodobne przypadki można wyeliminować, przechodząc na sortowanie sterty, jeśli stos rekurencyjny za głęboko. Tak więc TLDR polega na tym, że dla dobrych implementacji QuickSort, najgorszy przypadek tak naprawdę nie istnieje , ponieważ został zaprojektowany i wykonanie kończy się w czasie O(N*logn).

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

Chociaż oba są w tej samej klasie złożoności, nie oznacza to, że oba mają ten sam czas działania. Quicksort jest zwykle szybszy niż mergesort, tylko dlatego, że łatwiej jest zakodować ciasną implementację, a operacje, które wykonuje, mogą przebiegać szybciej. To dlatego, że quicksort jest na ogół szybszy, że ludzie używają go zamiast mergesort.

Jednak! Ja osobiście często będę używać mergesort lub quicksort wariant, który degraduje się do mergesort, gdy quicksort robi źle. Pamiętaj. Quicksort jest tylko O (n log n) na Średnia . Najgorsze jest O (n^2)! Mergesort jest zawsze O (N log n). W przypadkach, gdy wydajność w czasie rzeczywistym lub czas reakcji jest koniecznością, a dane wejściowe mogą pochodzić ze złośliwego źródła, nie powinieneś używać zwykłego quicksort.

Quicksort ma lepszą średnią złożoność sprawy, ale w niektórych aplikacjach jest to zły wybór. Quicksort jest podatny na ataki typu denial of service. Jeśli atakujący może wybrać Dane wejściowe, które mają być posortowane, może łatwo skonstruować zbiór, który zajmuje najgorsze złożoność czasu o (N^2).

Średnia złożoność przypadku Mergesorta i złożoność najgorszego przypadku są takie same i jako takie nie cierpią z tego samego problemu. Ta właściwość sortowania merge sprawia, że jest to najlepszy wybór w czasie rzeczywistym systemy-właśnie dlatego, że nie ma patologicznych przypadków, które powodują, że działa dużo, dużo wolniej.

Jestem większym fanem Mergesort niż Quicksort, z tych powodów.

Wszystkie rzeczy są równe, spodziewałbym się, że większość ludzi użyje tego, co jest najwygodniej dostępne, a to zwykle jest qsort(3). Poza tym quicksort jest znany jako bardzo szybki na tablicach, podobnie jak mergesort jest powszechnym wyborem dla list.

Zastanawiam się, dlaczego tak rzadko widuje się radix albo wiaderko. Są O (n), przynajmniej na linkowanych listach i wystarczy jakaś metoda konwersji klucza na numer porządkowy. (struny i pływaki działają dobrze.)

Myślę, że powód ma związek z tym, jak uczy się informatyki. Musiałem nawet zademonstrować mojemu wykładowcowi analizy algorytmów, że rzeczywiście możliwe jest sortowanie szybciej niż O(N log(n)). (Miał dowód, że nie można porównać sortować szybciej niż O(N log (n)), co jest prawdą.)

W innych wiadomościach, pływaki mogą być sortowane jako liczby całkowite, ale musisz potem odwrócić liczby ujemne.

Edytuj: Właściwie, to jest jeszcze bardziej złośliwy sposób sortowania floats-as-integers: http://www.stereopsis.com/radix.html . zauważ, że sztuczka z przerzucaniem bitów może być używana niezależnie od tego, jakiego algorytmu sortowania faktycznie używasz...

Trudno powiedzieć.Najgorsze jest n (log2n) - n+1, co jest dokładne, jeśli N równa się 2^k (już to udowodniłem).A dla dowolnego n jest pomiędzy (n lg n-N + 1) i (n lg n + n + O (lg n)).Ale dla quickSort, jego najlepszym jest nlog2n (również N równa się 2^k).Jeśli podzielisz Mergesort przez quickSort, to jest równy jeden, gdy n jest infinite.So to tak,jakby najgorszy przypadek MergeSort był lepszy niż najlepszy przypadek QuickSort, dlaczego używamy quicksort?Ale pamiętaj, MergeSort nie jest na miejscu, wymaga 2N memeroy miejsce.I MergeSort również trzeba wykonać wiele kopii tablic, których nie uwzględniamy w analizie algorithm.In słowo, MergeSort jest naprawdę szybszy niż quicksort w theroy, ale w rzeczywistości trzeba wziąć pod uwagę przestrzeń memeory, koszt kopii tablicy, fuzja jest wolniejsza niż szybkie sortowanie.Kiedyś zrobiłem eksperyment, w którym dostałem 1000000 cyfr w Javie przez losową klasę, i zajęło to 2610ms przez mergesort,1370ms przez quicksort.

Dlaczego Quicksort jest dobry?

• QuickSort bierze N^2 w najgorszym przypadku i nlogn średnia przypadku. Najgorszy przypadek występuje, gdy dane są sortowane. Może to być złagodzone przez losowe przetasowanie przed rozpoczęciem sortowania.
• QuickSort nie pobiera dodatkowej pamięci, która jest pobierana przez sortowanie scalające.
• Jeśli zbiór danych jest duży i istnieją identyczne elementy, złożoność Quicksort zmniejsza się za pomocą partycji 3-way. Więcej liczba identycznych przedmiotów lepiej sortować. Jeśli wszystkie elementy są identyczny, sortuje się w czasie liniowym. [Jest to domyślna implementacja w większości bibliotek]

Czy Quicksort jest zawsze lepszy niż Mergesort?

Nie bardzo.

• Mergesort jest stabilny, ale Quicksort nie. Więc jeśli potrzebujesz stabilności w wyjściu, użyjesz Mergesort. Stabilność jest wymagana w wielu praktycznych zastosowaniach.
Pamięć jest w dzisiejszych czasach tania. Więc jeśli dodatkowa pamięć używana przez Mergesort nie jest krytyczna dla Twojej aplikacji, nie ma szkody w korzystanie z Mergesort.

Uwaga: w języku java Tablice.funkcja sort() używa Quicksort dla prymitywnych typów danych i mergesort dla obiektowych typów danych. Ponieważ obiekty zużywają narzut pamięci, więc dodanie trochę narzutu dla Mergesort może nie być problemem z punktu widzenia wydajności.

Indeks : obejrzyj filmy QuickSort z Tydzień 3, Kurs algorytmów Princeton w Coursera

Szybkie sortowanie to najgorszy przypadek O( N^2), jednak średni przypadek konsekwentnie wykonuje sortowanie scalające. Każdy algorytm to O (nlogn), ale trzeba pamiętać, że mówiąc o dużym O pomijamy niższe czynniki złożoności. Szybkie sortowanie ma znaczną poprawę w stosunku do sortowania scalającego, jeśli chodzi o stałe czynniki.

Sortowanie scalające wymaga również pamięci o (2n) , podczas gdy szybkie sortowanie może być wykonywane w miejscu(wymaga tylko O (n)). Jest to kolejny powód, dla którego preferowane jest szybkie sortowanie over merge sort.

Dodatkowe informacje:

Najgorszy przypadek szybkiego sortowania występuje, gdy przegub jest źle wybrany. Rozważ następujący przykład:

[5, 4, 3, 2, 1]

Jeśli pivot zostanie wybrany jako najmniejsza lub największa liczba w grupie, szybkie sortowanie będzie działać w O (N^2). Prawdopodobieństwo wyboru elementu, który znajduje się w największym lub najmniejszym 25% listy, wynosi 0,5. Daje to algorytmowi 0,5 szansy na dobry obrót. Jeśli zastosujemy typowy pivot wybierając algorytm (powiedzmy wybierając element losowy), mamy 0,5 szansy na Wybór dobrego Pivota dla każdego wyboru Pivota. Dla zbiorów o dużych rozmiarach prawdopodobieństwo wyboru zawsze słabego obrotu wynosi 0,5 * N. na podstawie tego prawdopodobieństwa szybkie sortowanie jest efektywne dla przeciętnego (i typowego) przypadku.

W merge-sort ogólny algorytm jest następujący:

1. Sort the left sub-array
2. Sort the right sub-array
3. Scalanie 2 posortowanych tablic podrzędnych

Na najwyższym poziomie, scalanie 2 posortowanych pod-tablic polega na radzeniu sobie z N elementami.

O jeden poziom niżej, każda iteracja kroku 3 obejmuje radzenie sobie z N / 2 elementami, ale musisz powtórzyć ten proces dwa razy. Więc nadal masz do czynienia z 2 * N/2 == N elementów.

Jeden poziom niżej, jesteś łączenie 4 * N / 4 == N elementów i tak dalej. Każda głębokość w stosie rekurencyjnym polega na łączeniu tej samej liczby elementów, we wszystkich wywołaniach tej głębokości.

Zamiast tego Rozważ algorytm szybkiego sortowania:

1. Wybierz punkt obrotu
2. umieść punkt obrotu w odpowiednim miejscu w tablicy, ze wszystkimi mniejszymi elementami po lewej stronie, a większymi po prawej
3. Sort the left-subarray
4. Sort the right-subarray

Na najwyższym poziomie jesteś radzenie sobie z tablicą o rozmiarze N. następnie wybierasz jeden punkt obrotu, umieszczasz go w prawidłowej pozycji, a następnie możesz go całkowicie zignorować przez resztę algorytmu.

Jeden poziom poniżej, masz do czynienia z 2 podzakresami, które mają łączny rozmiar N - 1 (tj. odjąć wcześniejszy punkt obrotu). Wybierz punkt obrotu dla każdej tablicy podrzędnej, który pojawia się do 2 dodatkowych punktów obrotu.

Jeden poziom poniżej tego, masz do czynienia z 4 sub-tablicami o łącznym rozmiarze N-3, z tych samych powodów jak wyżej.

Następnie N-7... Potem N-15... Potem N-32...

Głębokość stosu rekurencyjnego pozostaje w przybliżeniu taka sama (logN). Z merge-sort, zawsze masz do czynienia z N-elementowym scaleniem, na każdym poziomie stosu rekurencyjnego. W przypadku szybkiego sortowania liczba elementów, z którymi masz do czynienia, zmniejsza się wraz z upływem czasu. Na przykład, jeśli spojrzysz na głębokość w połowie stosu rekurencyjnego, liczba elementów, z którymi masz do czynienia, wynosi N - 2^((logN)/2)) == N-sqrt (N).

Disclaimer: przy merge-sort, ponieważ dzielisz tablicę na 2 dokładnie równe kawałki za każdym razem, głębokość rekurencyjna jest dokładnie logN. W przypadku szybkiego sortowania, ponieważ jest mało prawdopodobne, aby punkt obrotu znajdował się dokładnie w środku tablicy, głębokość stosu rekurencyjnego może być nieco większa niż logN. Nie zrobiłem matematyki, aby zobaczyć, jak dużą rolę ten czynnik i czynnik opisany powyżej, faktycznie odgrywają w złożoności algorytmu.

Kiedy eksperymentowałem z obydwoma algorytmami sortowania, licząc liczbę wywołań rekurencyjnych, quicksort konsekwentnie ma mniej wywołań rekurencyjnych niż mergesort. Dzieje się tak dlatego, że quicksort ma sworznie, a sworznie nie są uwzględniane w kolejnych wywołaniach rekurencyjnych. W ten sposób quicksort może szybciej dotrzeć do rekurencyjnej bazy case niż mergesort.

W przeciwieństwie do sortowania scalonego szybkie sortowanie nie używa spacji pomocniczej. Natomiast sortowanie Merge używa przestrzeni pomocniczej O (n). Ale sortowanie Merge ma najgorszą złożoność czasową O(nlogn), podczas gdy najgorsza złożoność szybkiego sortowania to O (N^2), co dzieje się, gdy tablica jest już posortowana.

Małe dodatki do sortów quick vs merge.

Również może zależeć od rodzaju sortowania elementów. Jeśli dostęp do elementów, zamiany i porównania nie są prostymi operacjami, takimi jak porównywanie liczb całkowitych w pamięci płaszczyznowej, to preferowanym algorytmem może być sortowanie scalające.

Na przykład sortujemy elementy za pomocą protokołu sieciowego na zdalnym serwerze.

Również w niestandardowych kontenerach, takich jak" linked list", nie ma korzyści z szybkiego sortowania.
1. Sortuj scalanie na liście połączonej, nie potrzebujesz dodatkowych pamięć. 2. Dostęp do elementów w szybkim sortowaniu nie jest sekwencyjny (w pamięci)

Należy wziąć pod uwagę również pamięć. Mergesort wymaga dodatkowej tablicy, powiedzmy "tablicy obszaru roboczego". Jeśli twoja pamięć jest ledwo wystarczająco duża, aby przechowywać oryginalną tablicę, mergesort nie będzie działać.

Szybkie sortowanie jest algorytmem sortowania w miejscu, więc lepiej nadaje się do tablic. Z drugiej strony sortowanie scalające wymaga dodatkowego przechowywania O (N) i jest bardziej odpowiednie dla list połączonych.

W przeciwieństwie do tablic, w liście liked możemy wstawiać pozycje w środku o(1) spacji i o(1) czasu, dlatego operacja merge w sortowaniu merge może być zaimplementowana bez dodatkowej spacji. Jednak przydzielanie i dealowanie dodatkowej przestrzeni dla tablic ma niekorzystny wpływ na czas wykonywania sortowania scalającego. Sortowanie scalające sprzyja również liście połączonej, ponieważ dane są dostępne sekwencyjnie, bez większego losowego dostępu do pamięci.

Szybkie sortowanie z drugiej strony wymaga dużo losowego dostępu do pamięci i za pomocą tablicy możemy bezpośrednio uzyskać dostęp do pamięci bez przechodzenia przez nią, zgodnie z wymaganiami połączonych list. Również szybkie sortowanie w przypadku tablic ma dobrą lokalizację odniesienia, ponieważ tablice są przechowywane w pamięci.

Mimo że oba algorytmy sortowania średnia złożoność wynosi O (NlogN), zwykle ludzie dla zwykłych zadań używa tablicy do przechowywania i z tego powodu szybkie sortowanie powinno być algorytmem wyboru.

EDIT: właśnie się dowiedziałem, że sortowanie merge worst / best / avg jest zawsze nlogn, ale szybkie sortowanie może się różnić od n2(najgorszy przypadek, gdy elementy są już posortowane) do nlogn (avg/najlepszy przypadek, gdy pivot zawsze dzieli tablicę na dwie połówki).

To jest dość stare pytanie, ale ponieważ mam do czynienia z obu ostatnio tutaj są moje 2C:

Sortowanie scalające wymaga średnio ~ N log N porównań. Dla już (prawie) posortowanych tablic spadnie to do 1/2 n log N, ponieważ podczas scalania (prawie) zawsze wybieramy "lewą" część 1/2 N razy, a następnie kopiujemy prawą 1/2 N elementów. Dodatkowo mogę spekulować, że już posortowane wejście sprawia, że predyktor gałęzi procesora świeci, ale odgadywanie prawie wszystkich gałęzi poprawnie, zapobiegając stragany rurociągów.

Szybkie sortowanie średnio wymaga ~ 1.38 n log N porównań. Nie przynosi on większych korzyści z już posortowanej tablicy pod względem porównań(jednak ma to miejsce pod względem swapów i prawdopodobnie pod względem przewidywania gałęzi wewnątrz procesora).

Moje benchmarki na dość nowoczesnym procesorze pokazują co następuje:

Gdy funkcja porównawcza jest funkcją wywołania zwrotnego (jak w implementacji qsort () libc), quicksort jest wolniejszy od mergesort o 15% przy losowym wejściu i 30% dla już posortowana tablica dla 64 bitowych liczb całkowitych.

Z drugiej strony, jeśli porównanie nie jest callback, moje doświadczenie jest takie, że quicksort przewyższa mergesort nawet o 25%.

Jeśli jednak twoja (duża) tablica ma bardzo niewiele unikalnych wartości, sortowanie scalające w każdym przypadku zaczyna zyskiwać na quicksort.

Więc może chodzi o to, że jeśli porównanie jest drogie (np. funkcja zwrotna, porównywanie ciągów, porównywanie wielu części struktury najczęściej do drugiego-trzeciego "Jeśli", aby różnica) - są szanse, że będzie lepiej z sortowania merge. Dla prostszych zadań quicksort będzie szybszy.

To wszystko, co wcześniej powiedziane, jest prawdą: - Quicksort może być N^2, ale Sedgewick twierdzi, że dobra implementacja randomizowana ma większe szanse na to, że komputer wykonujący sort zostanie uderzony przez piorun niż na N^2 - Mergesort wymaga dodatkowej przestrzeni

W C / C++ land, gdy nie używam kontenerów stl, zwykle używam quicksort, ponieważ jest zbudowany do czasu uruchomienia, podczas gdy mergesort nie jest.

Uważam więc, że w wielu przypadkach jest to po prostu droga najmniejszego oporu.

Ponadto wydajność może być znacznie wyższa dzięki quick sort, w przypadkach, gdy cały zestaw danych nie pasuje do zestawu roboczego.

Jeden z powodów jest bardziej filozoficzny. Quicksort to filozofia Top- > Down. Z N elementów do sortowania, jest n! możliwości. Z 2 partycjami m & n - m, które wzajemnie się wykluczają, liczba możliwości spada w kilku rzędach wielkości. m! * (n-m)! jest mniejszy o kilka zamówień niż n! sam. wyobraź sobie 5! vs 3! *2!. 5! ma 10 razy więcej możliwości niż 2 partycje po 2 i 3 każda . i ekstrapolować do 1 miliona czynników vs 900K!* 100K! vs. więc zamiast martwić się o ustalanie dowolnego porządku w zakresie lub partycji, po prostu ustal porządek na szerszym poziomie w partycjach i zmniejsz możliwości wewnątrz partycji. Każdy porządek ustalony wcześniej w zakresie zostanie zakłócony później, jeśli same partycje nie wykluczają się wzajemnie.

Każde podejście typu "bottom up order", takie jak sortowanie scalające lub sortowanie sterty, jest podobne do podejścia pracownika lub pracownika, w którym zaczyna się porównywać NA mikroskopijnym poziomie wcześnie. Ale ten rozkaz jest zobowiązany do utraty, jak tylko element pomiędzy nimi znajduje się później. Te podejścia są bardzo stabilne i niezwykle przewidywalne, ale wykonują pewną ilość dodatkowej pracy.

Szybkie sortowanie jest jak podejście menedżerskie, w którym początkowo nie chodzi o żadne zamówienie , tylko o spełnienie szerokiego kryterium bez względu na porządek. Następnie partycje są zawężane, aż otrzymasz posortowany zestaw. Prawdziwym wyzwaniem w Quicksort jest znalezienie partycji lub kryterium w ciemności, gdy nie wiesz nic o elementach do Sortuj. Dlatego musimy albo poświęcić trochę wysiłku, aby znaleźć wartość medianą, albo wybrać 1 losowo lub dowolne podejście "menedżerskie". Znalezienie idealnej mediany może zająć znaczną ilość wysiłku i prowadzi do głupiego oddolnego podejścia. Więc Quicksort mówi po prostu wybrać losowy pivot i mam nadzieję, że będzie gdzieś w środku lub wykonaj jakąś pracę, aby znaleźć medianę 3, 5 lub coś więcej, aby znaleźć lepszą medianę, ale nie planuj być idealnym & nie trać czasu na początku zamawiam. To wydaje się zrobić dobrze, jeśli masz szczęście lub czasami degraduje się do n^2, gdy nie masz mediany, ale po prostu zaryzykować. Dowolne dane są losowe. racja. Więc zgadzam się bardziej z logicznym podejściem top - > down quicksort i okazuje się, że szansa na wybór Pivota i porównania, które oszczędza wcześniej, wydaje się działać lepiej więcej razy niż jakiekolwiek skrupulatne i dokładne stabilne podejście bottom ->up, takie jak sortowanie scalające. Ale