Dlaczego Quicksort jest lepszy od FusionSort?

Zadano mi to pytanie podczas wywiadu. Obaj są O (nlogn), a jednak większość ludzi używa Quicksort zamiast Mergesort. Dlaczego?

Quicksort ma czas działania w najgorszym przypadku O ( n ² ) i średni czas wykonania O ( n log n ). Jednak lepsze jest scalanie sortowania w wielu scenariuszach, ponieważ wiele czynników wpływa na środowisko uruchomieniowe algorytmu, a biorąc je wszystkie razem, wygrywa Quicksort.

W szczególności często cytowane środowisko wykonawcze algorytmów sortowania odnosi się do liczby porównań lub liczby zamian niezbędnych do przeprowadzenia sortowania danych. Jest to rzeczywiście dobra miara wydajności, zwłaszcza, że ​​jest niezależna od podstawowej konstrukcji sprzętu. Jednak inne rzeczy - takie jak lokalizacja odniesienia (tj. Czy czytamy wiele elementów, które prawdopodobnie znajdują się w pamięci podręcznej?) - również odgrywają ważną rolę na obecnym sprzęcie. W szczególności Quicksort wymaga niewielkiej dodatkowej przestrzeni i wykazuje dobrą lokalizację pamięci podręcznej, co sprawia, że ​​w wielu przypadkach jest szybsza niż sortowanie przez scalanie.

Ponadto bardzo łatwo jest uniknąć prawie w całości najgorszego czasu szybkiego uruchamiania O ( n ² ), stosując odpowiedni wybór osi przestawnej - na przykład wybranie go losowo (jest to doskonała strategia).

W praktyce wiele współczesnych implementacji quicksort (w szczególności libstdc ++ std::sort) jest w rzeczywistości introsortami , których teoretycznie najgorszym przypadkiem jest O ( n log n ), podobnie jak sortowanie po scaleniu. Osiąga to poprzez ograniczenie głębokości rekurencji i przełączenie na inny algorytm ( heapsort ), gdy przekroczy log n .

Jak zauważyło wiele osób, średnia wydajność sprawy w przypadku szybkiego sortowania jest szybsza niż w przypadku scalania. Ale jest to prawdą tylko wtedy, gdy zakładasz stały czas dostępu do dowolnej części pamięci na żądanie.

W pamięci RAM to założenie zasadniczo nie jest takie złe (nie zawsze jest prawdziwe z powodu pamięci podręcznych, ale nie jest tak źle). Jeśli jednak twoja struktura danych jest wystarczająco duża, aby pomieścić na dysku, to Quicksort zostaje zabity przez fakt, że przeciętny dysk wykonuje około 200 losowych prób na sekundę. Ale ten sam dysk nie ma problemów z sekwencyjnym odczytem lub zapisem megabajtów danych na sekundę. To właśnie robi scalanie.

Dlatego jeśli dane muszą być sortowane na dysku, naprawdę, naprawdę chcesz skorzystać z pewnej odmiany w scalesort. (Ogólnie rzecz biorąc, szybko sortujesz podlisty, a następnie zaczynasz je scalać powyżej pewnego progu wielkości).

Co więcej, jeśli musisz coś zrobić z zestawami danych o takim rozmiarze, zastanów się, jak uniknąć szukania dysku. Na przykład dlatego standardową wskazówką jest usunięcie indeksów przed wykonaniem dużych ładowań danych w bazach danych, a następnie odbudowanie indeksu później. Utrzymywanie indeksu podczas ładowania oznacza ciągłe szukanie dysku. Z drugiej strony, jeśli upuścisz indeksy, baza danych może odbudować indeks, najpierw sortując informacje, którymi należy się zająć (używając oczywiście połączenia), a następnie ładując je do struktury danych BTREE dla indeksu. (BTREE są naturalnie utrzymywane w porządku, więc możesz załadować jeden z posortowanego zestawu danych z kilkoma próbami na dysku).

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

W rzeczywistości QuickSort to O (n ² ). Jego przeciętna sprawa czas trwania wynosi O (nlog (n)), ale jego najgorszym przypadku wynosi O (n ² ), która pojawia się po uruchomieniu go na liście, która zawiera kilka unikalnych przedmiotów. Randomizacja przyjmuje O (n). Oczywiście nie zmienia to najgorszego przypadku, po prostu zapobiega złośliwemu użytkownikowi, który zajmuje dużo czasu.

QuickSort jest bardziej popularny, ponieważ:

1. Jest na miejscu (MergeSort wymaga dodatkowej pamięci liniowej względem liczby elementów do posortowania).
2. Ma małą ukrytą stałą.

„a jednak większość ludzi używa Quicksort zamiast Mergesort. Dlaczego tak jest?”

Jednym z psychologicznych powodów, których nie podano, jest po prostu to, że Quicksort jest sprytniej nazwany. tj. dobry marketing.

Tak, Quicksort z potrójnym partycjonowaniem jest prawdopodobnie jednym z najlepszych algorytmów sortowania ogólnego przeznaczenia, ale nie można pominąć faktu, że sortowanie „szybkie” brzmi o wiele mocniej niż sortowanie „scalające”.

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

Tym, co sprawia, że ​​Quicksort jest lepszy, jest to, że wewnętrzna pętla oznacza porównanie kilku wartości z jedną, podczas gdy z drugiej strony oba warunki są różne dla każdego porównania. Innymi słowy, Quicksort wykonuje o połowę mniej odczytów niż pozostałe dwa algorytmy. Na współczesnych procesorach wydajność jest w dużej mierze zdominowana przez czasy dostępu, więc ostatecznie Quicksort jest doskonałym pierwszym wyborem.

Chciałbym dodać, że z trzech wspomnianych dotychczas algorytmów (scalesort, quicksort i sortowanie sterty) tylko scalesort 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, a szybkie sortowanie jest ... szybkie =)

Wszystkie algorytmy sortowania mają swoje wzloty i upadki. Dobry przegląd można znaleźć w artykule na temat algorytmów sortowania .

Z pozycji Wikipedii w Quicksort :

Quicksort konkuruje również z scalesort, innym algorytmem sortowania rekurencyjnego, ale z korzyścią dla czasu działania w najgorszym przypadku n (nlogn). Mergesort jest stabilnym rodzajem, w przeciwieństwie do Quicksort i Heapsort, i można go łatwo dostosować do działania na listach połączonych i bardzo dużych listach przechowywanych na wolno dostępnych nośnikach, takich jak pamięć dyskowa lub pamięć podłączona do sieci. Chociaż Quicksort może być napisany do działania na połączonych listach, często cierpi z powodu złych wyborów przestawnych bez losowego dostępu. Główną wadą programu Combesort jest to, że podczas pracy na tablicach wymaga w najlepszym przypadku Θ (n) przestrzeni pomocniczej, podczas gdy wariant Quicksort z partycjonowaniem w miejscu i rekurencją ogona wykorzystuje tylko Θ (logn). (Należy pamiętać, że podczas pracy na połączonych listach, połączenie wymaga tylko niewielkiej, stałej ilości pamięci dyskowej.)

Mu! Quicksort nie jest lepszy, jest dobrze przystosowany do innego rodzaju aplikacji niż scalesort.

Mergesort jest warty rozważenia, jeśli szybkość jest najważniejsza, zła wydajność w najgorszym przypadku nie może być tolerowana, a dostępna jest dodatkowa przestrzeń. 1

Stwierdziłeś, że «Oboje są O (nlogn) […]». To jest źle. «W najgorszym przypadku Quicksort używa około porównań n ^ 2/2.» 1 .

Jednak najważniejszą właściwością według mojego doświadczenia jest łatwa implementacja dostępu sekwencyjnego, z którego można korzystać podczas sortowania podczas używania języków programowania z imperatywnym paradygmatem.

1 Sedgewick, Algorytmy

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

Heapsort gwarantuje działanie w O (n * ln (n)) i wymaga tylko skończonej dodatkowej pamięci. Istnieje jednak wiele cytatów z prawdziwych testów, które pokazują, że heapsort jest średnio wolniejszy niż Quicksort.

Wyjaśnienie Wikipedii jest następujące:

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

Szybkie sortowanie

Mergesort

Myślę, że istnieją również problemy z ilością miejsca potrzebną na Mergesort (czyli Ω (n)), której nie mają implementacje Quicksort. W najgorszym przypadku mają taki sam czas algorytmiczny, ale scalanie wymaga więcej pamięci.

Chciałbym dodać do istniejących świetnych odpowiedzi trochę matematyki na temat tego, jak działa QuickSort po odejściu od najlepszego przypadku i jak prawdopodobne jest to, co, mam nadzieję, pomoże ludziom lepiej zrozumieć, dlaczego przypadek O (n ^ 2) nie jest prawdziwy troska o bardziej wyrafinowane implementacje QuickSort.

Oprócz problemów z dostępem swobodnym istnieją dwa główne czynniki, które mogą wpłynąć na wydajność QuickSort i oba są związane z tym, jak oś przestawna porównuje z sortowanymi danymi.

1) Mała liczba kluczy w danych. Zbiór danych o tej samej wartości zostanie posortowany w czasie n ^ 2 na waniliowym QuickSort z 2 partycjami, ponieważ wszystkie wartości oprócz położenia przestawnego są umieszczane po jednej stronie za każdym razem. Nowoczesne implementacje rozwiązują ten problem metodami, takimi jak sortowanie z 3 partycjami. Te metody działają na zbiorze danych o tej samej wartości w czasie O (n). Zatem użycie takiej implementacji oznacza, że ​​dane wejściowe z małą liczbą kluczy faktycznie skracają czas działania i nie stanowią już problemu.

2) Bardzo zły wybór osi obrotu może spowodować najgorsze działanie przypadku. W idealnym przypadku oś obrotu będzie zawsze taka, że ​​50% danych jest mniejsze, a 50% danych jest większe, tak że dane wejściowe będą dzielone na pół podczas każdej iteracji. To daje nam n porównań i czasów zamiany log-2 (n) rekurencji dla czasu O (n * logn).

Jak bardzo nieidealny wybór osi obrotu wpływa na czas wykonania?

Rozważmy przypadek, w którym oś przestawna jest konsekwentnie wybierana tak, że 75% danych znajduje się po jednej stronie osi przestawnej. Nadal jest to O (n * logn), ale teraz podstawa logu zmieniła się na 1 / 0,75 lub 1,33. Zależność w 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 jakość wyboru osi obrotu zajmuje 2,4 razy dłużej niż ideał.

Jak szybko to się pogarsza?

Niezbyt szybko, dopóki wybór przestawienia nie stanie się (konsekwentnie) bardzo zły:

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

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

W naiwnej implementacji QuickSort przypadki, takie jak sortowana tablica (dla pierwszego elementu przestawnego) lub odwrócona sortowana tablica (dla ostatniego elementu przestawnego) niezawodnie wygenerują czas wykonania O (n ^ 2) w najgorszym przypadku. Ponadto implementacje z przewidywalnym wyborem przestawnym mogą zostać poddane atakowi DoS przez dane zaprojektowane w taki sposób, aby powodować najgorsze wykonanie. Nowoczesne implementacje unikają tego za pomocą różnych metod, takich jak randomizacja danych przed sortowaniem, wybranie mediany z 3 losowo wybranych indeksów itp. Przy tej losowości w mieszance mamy 2 przypadki:

• Mały zestaw danych. Najgorszy przypadek jest racjonalnie możliwy, ale O (n ^ 2) nie jest katastrofalne, 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 okropne wyniki?

Szanse są znikomo małe . Rozważmy coś w rodzaju 5000 wartości:

Nasza hipotetyczna implementacja wybierze oś obrotu za pomocą mediany 3 losowo wybranych indeksów. Uważamy, że pivoty z przedziału 25% -75% są „dobre”, a pivots z przedziału 0% -25% lub 75% -100% za „złe”. Jeśli spojrzysz na rozkład prawdopodobieństwa za pomocą mediany 3 losowych indeksów, każda rekurencja ma szansę 11/16 na koniec z dobrym przestawieniem. Zróbmy 2 konserwatywne (i fałszywe) założenia, aby uprościć matematykę:

1. Dobre czopy są zawsze dokładnie w proporcji 25% / 75% i działają w idealnym przypadku 2,4 *. Nigdy nie otrzymujemy idealnego podziału ani żadnego podziału lepszego niż 25/75.

2. Złe punkty zwrotne są zawsze najgorszym przypadkiem i zasadniczo nie przyczyniają się do rozwiązania.

Nasza implementacja QuickSort zatrzyma się przy n = 10 i przełączy się na rodzaj wstawiania, więc potrzebujemy 22 25% / 75% przestawnych partycji, aby złamać do tej pory 5000 wartości wejściowych. (10 * 1.333333 ^ 22> 5000) Lub, potrzebujemy 4990 osi najgorszego przypadku. Należy pamiętać, że jeśli zgromadzimy 22 dobre punkty obrotu w dowolnym momencie, sortowanie zakończy się, więc najgorszy przypadek lub coś w pobliżu wymaga wyjątkowo pecha. Gdyby zajęło nam 88 rekurencji, aby faktycznie osiągnąć 22 dobre punkty obrotu wymagane do posortowania do n = 10, byłby to idealny przypadek 4 * 2,4 * lub około 10-krotny czas wykonania idealnego przypadku. Jak prawdopodobne jest, że po 88 rekurencjach nie osiągnęlibyśmy wymaganych 22 dobrych osi obrotu?

Dwumianowe rozkłady prawdopodobieństwa mogą na to odpowiedzieć, a odpowiedź wynosi około 10 ^ -18. (n to 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 potrzebnej do kliknięcia [SORTUJ], niż gdy zobaczy, że 5000 sortowanych przedmiotów działa gorzej niż 10 * idealny przypadek. Ta szansa maleje wraz ze wzrostem zbioru danych. Oto niektóre rozmiary tablic i odpowiadające im szanse na uruchomienie dłuższe niż 10 * idealne:

• Tablica 640 przedmiotów: 10 ^ -13 (wymaga 15 dobrych punktów obrotu na 60 prób)
• Tablica 5000 przedmiotów: 10 ^ -18 (wymaga 22 dobrych osi obrotu z 88 prób)
• Tablica 40 000 przedmiotów: 10 ^ -23 (wymaga 29 dobrych osi obrotu na 116)

Pamiętaj, że dzieje się tak przy 2 konserwatywnych założeniach, które są gorsze od rzeczywistości. Tak więc rzeczywista wydajność jest jeszcze lepsza, a bilans pozostałego prawdopodobieństwa jest bliższy ideału niż nie.

Wreszcie, jak wspomnieli inni, nawet te absurdalnie mało prawdopodobne przypadki można wyeliminować, przełączając się na rodzaj stosu, jeśli stos rekurencyjny pójdzie zbyt głęboko. Zatem TLDR jest taki, że dla dobrych implementacji QuickSort najgorszy przypadek tak naprawdę nie istnieje, ponieważ został zaprojektowany i wykonanie kończy się w czasie O (n * logn).

Dlaczego Quicksort jest dobry?

• QuickSort przyjmuje N ^ 2 w najgorszym przypadku i NlogN średni przypadek. Najgorszy przypadek występuje podczas sortowania danych. Można to złagodzić losowym losowaniem przed rozpoczęciem sortowania.
• QuickSort nie zajmuje dodatkowej pamięci zajmowanej przez sortowanie po scaleniu.
• Jeśli zestaw danych jest duży i istnieją identyczne elementy, złożoność Quicksort zmniejsza się dzięki zastosowaniu partycji 3-kierunkowej. Im więcej identycznych produktów, tym lepiej. Jeśli wszystkie elementy są identyczne, sortuje się w czasie liniowym. [Jest to domyślna implementacja w większości bibliotek]

Czy Quicksort jest zawsze lepszy niż Mergesort?

Nie całkiem.

• Mergesort jest stabilny, ale Quicksort nie. Więc jeśli potrzebujesz stabilności produkcji, skorzystaj z Mergesort. W wielu praktycznych zastosowaniach wymagana jest stabilność.
• Pamięć jest obecnie tania. Jeśli więc dodatkowa pamięć używana przez Mergesort nie jest krytyczna dla twojej aplikacji, korzystanie z Mergesort nie zaszkodzi.

Uwaga: W java funkcja Arrays.sort () używa Quicksort dla pierwotnych typów danych i Mergesort dla typów danych obiektowych. Ponieważ obiekty zużywają narzut pamięci, więc dodanie niewielkiego narzutu dla Mergesort może nie stanowić żadnego problemu z punktu widzenia wydajności.

Odniesienie : Obejrzyj filmy QuickSort z Tygodnia 3, Princeton Al Algorytmy Course at Coursera

Quicksort NIE jest lepszy niż scalanie. W przypadku O (n ^ 2) (najgorszy przypadek, który rzadko się zdarza), szybkie sortowanie jest potencjalnie znacznie wolniejsze niż O (nlogn) w rodzaju scalania. Quicksort ma mniejszy narzut, więc przy małych komputerach i powolnych komputerach jest lepiej. Ale komputery są dziś tak szybkie, że dodatkowe obciążenie połączenia jest znikome, a ryzyko bardzo wolnego szybkiego połączenia znacznie przewyższa nieznaczne obciążenie połączenia.

Ponadto scalanie pozostawia elementy z identycznymi kluczami w ich oryginalnej kolejności, co jest użytecznym atrybutem.

Odpowiedź nieznacznie pochyliłaby się w kierunku szybkiego zapisu do zmian wprowadzonych za pomocą DualPivotQuickSort dla prymitywnych wartości. Jest używany w JAVA 7 do sortowania w java.util.Arrays

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.

Wdrożenie JAVA7 można znaleźć 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

W sortowaniu według scalania algorytmem ogólnym jest:

1. Posortuj lewą macierz podrzędną
2. Posortuj odpowiednią pod-tablicę
3. Scal 2 posortowane pod-tablice

Na najwyższym poziomie scalenie 2 posortowanych pod-tablic wiąże się z obsługą N elementów.

Jeden poziom poniżej tego, każda iteracja kroku 3 wymaga radzenia sobie z N / 2 elementami, ale musisz powtórzyć ten proces dwa razy. Więc nadal masz do czynienia z 2 * N / 2 == N elementami.

Jeden poziom poniżej łączysz 4 * N / 4 == N elementów i tak dalej. Każda głębokość w stosie rekurencyjnym wymaga scalenia 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 we właściwym miejscu w szyku, ze wszystkimi mniejszymi elementami po lewej, a większymi elementami po prawej
3. Posortuj lewą podtablicę
4. Posortuj prawą pod-tablicę

Na najwyższym poziomie masz do czynienia z tablicą o rozmiarze N. Następnie wybierasz jeden punkt obrotu, ustawiasz go we właściwej pozycji, a następnie możesz całkowicie go zignorować dla pozostałej części algorytmu.

Jeden poziom poniżej masz do czynienia z 2 pod-macierzami, które mają łączny rozmiar N-1 (tj. Odejmij wcześniejszy punkt obrotu). Wybierasz punkt obrotu dla każdej pod-macierzy, co daje 2 dodatkowe punkty obrotu.

Jeden poziom poniżej masz do czynienia z 4 pod-macierzami o połączonym rozmiarze N-3, z tych samych powodów, co powyżej.

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

Głębokość stosu rekurencyjnego pozostaje w przybliżeniu taka sama (logN). Dzięki sortowaniu według scalania zawsze masz do czynienia z łączeniem N-elementowym na każdym poziomie stosu rekurencyjnego. Dzięki szybkiemu sortowaniu liczba elementów, z którymi masz do czynienia, zmniejsza się wraz ze spadkiem stosu. Na przykład, jeśli spojrzysz na głębokość w połowie stosu rekurencyjnego, liczba elementów, z którymi masz do czynienia, to N - 2 ^ ((logN) / 2)) == N - sqrt (N).

Uwaga: Przy sortowaniu według scalania, ponieważ za każdym razem dzielisz tablicę na 2 dokładnie równe porcje, głębokość rekurencyjna wynosi dokładnie logN. Podczas szybkiego sortowania, ponieważ jest mało prawdopodobne, aby punkt obrotu znajdował się dokładnie na ś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 odgrywają w złożoności algorytmu.

W przeciwieństwie do sortowania scalonego Szybkie sortowanie nie wykorzystuje przestrzeni pomocniczej. Natomiast sortowanie korespondencji wykorzystuje przestrzeń pomocniczą O (n). Ale sortowanie korespondencji seryjnej ma najgorszą złożoność przypadków O (nlogn), podczas gdy najgorszą złożoność szybkiego sortowania stanowi O (n ^ 2), co ma miejsce, gdy tablica jest już posortowana.

Quicksort ma lepszą średnią złożoność spraw, ale w niektórych aplikacjach jest to zły wybór. Quicksort jest podatny na ataki typu „odmowa usługi”. Jeśli atakujący może wybrać dane wejściowe do posortowania, może łatwo skonstruować zestaw, który zajmuje najgorszy przypadek złożoności o (n ^ 2).

Średnia złożoność przypadku Mergesort i najgorsza złożoność przypadku są takie same i jako takie nie mają tego samego problemu. Ta właściwość sortowania według scalania czyni ją również najlepszym wyborem dla systemów czasu rzeczywistego - właśnie dlatego, że nie ma przypadków patologicznych, które powodują, że działa ona znacznie, znacznie wolniej.

Z tych powodów jestem większym fanem Mergesortu niż Quicksorta.

Trudno powiedzieć. Najgorsze z MergeSort to n (log2n) -n + 1, co jest dokładne, jeśli n jest równe 2 ^ k (już to udowodniłem). A dla dowolnego n, to jest pomiędzy (n lg n - n + 1) i (n lg n + n + O (lg n)). Ale dla quickSort najlepiej jest nlog2n (także n równa się 2 ^ k). Jeśli dzielisz Mergesort przez quickSort, jest równy jeden, gdy n jest nieskończony. to tak, jakby najgorszy przypadek MergeSort był lepszy niż najlepszy przypadek QuickSort, dlaczego używamy Quicksort? Pamiętaj jednak, że MergeSort nie jest na miejscu, wymaga 2 miejsca w pamięci i MergeSort musi również wykonać wiele kopii tablicy, które my nie uwzględniaj w analizie algorytmu. Jednym słowem, MergeSort jest naprawdę bardziej fasetowy niż quicksort w theroy, ale w rzeczywistości musisz wziąć pod uwagę miejsce w pamięci, koszt kopiowania tablicy, połączenie jest wolniejsze niż szybkie sortowanie. eksperyment, w którym otrzymałem 1000000 cyfr w Javie od klasy Random,i zajęło 2610 ms przez scalesort, 1370 ms przez quicksort.

Szybkie sortowanie jest najgorszym przypadkiem O (n ^ 2), jednak przeciętny przypadek konsekwentnie wykonuje sortowanie scalone. Każdy algorytm to O (nlogn), ale musisz pamiętać, że mówiąc o Big O pomijamy czynniki o niższej złożoności. Szybkie sortowanie ma znaczną poprawę w stosunku do sortowania scalonego, jeśli chodzi o stałe czynniki.

Sortowanie z sortowaniem wymaga również pamięci O (2n), natomiast szybkie sortowanie można wykonać na miejscu (wymagając tylko O ​​(n)). Jest to kolejny powód, dla którego szybkie sortowanie jest ogólnie preferowane niż sortowanie scalone.

Informacje dodatkowe:

Najgorszy przypadek szybkiego sortowania występuje, gdy oś obrotu jest źle wybrana. Rozważ następujący przykład:

[5, 4, 3, 2, 1]

Jeśli oś przestawna zostanie wybrana jako najmniejsza lub największa liczba w grupie, szybkie sortowanie rozpocznie się w O (n ^ 2). Prawdopodobieństwo wyboru elementu znajdującego się w największej lub najmniejszej 25% listy wynosi 0,5. To daje algorytmowi 0,5 szansy na bycie dobrym pivotem. Jeśli zastosujemy typowy algorytm wyboru osi przestawnej (np. Wybranie elementu losowego), mamy 0,5 szansy na wybranie dobrego elementu przestawnego dla każdego wyboru osi przestawnej. W przypadku kolekcji o dużych rozmiarach prawdopodobieństwo zawsze wybrania złej osi obrotu wynosi 0,5 * n. Na podstawie tego prawdopodobieństwa szybkie sortowanie jest skuteczne w przypadku przeciętnego (i typowego) przypadku.

To dość stare pytanie, ale ponieważ ostatnio zajmowałem się obydwoma, oto moje 2c:

Scal sortowanie potrzebuje średnio ~ N log N porównań. W przypadku już (prawie) posortowanych tablic posortowanych sprowadza się to do 1/2 N log N, ponieważ podczas scalania (prawie) zawsze wybieramy „lewą” część 1/2 N razy, a następnie po prostu kopiujemy prawe 1/2 N elementów. Dodatkowo mogę spekulować, że już posortowane dane wejściowe sprawiają, że predyktor gałęzi procesora świeci, ale poprawnie zgaduję prawie wszystkie gałęzie, zapobiegając w ten sposób zablokowaniu rurociągu.

Średnio szybkie sortowanie wymaga ~ 1,38 N log N porównań. Nie korzysta on zbytnio z już posortowanej tablicy pod względem porównań (jednak robi to pod względem swapów i prawdopodobnie pod względem prognoz rozgałęzień w CPU).

Moje testy porównawcze na dość nowoczesnym procesorze pokazują:

Gdy funkcja porównania jest funkcją wywołania zwrotnego (jak w implementacji qsort () libc), szybkie sortowanie jest wolniejsze niż scalanie o 15% na losowych danych wejściowych i 30% dla już posortowanej tablicy dla 64-bitowych liczb całkowitych.

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

Jeśli jednak twoja (duża) tablica ma bardzo kilka unikalnych wartości, sortowanie scalające zaczyna w każdym przypadku uzyskiwać więcej niż szybkie sortowanie.

Więc może sedno brzmi: jeśli porównanie jest drogie (np. Funkcja zwrotna, porównywanie ciągów, porównywanie wielu części struktury, w większości przechodzenie do drugiej trzeciej czwartej „jeśli”, aby coś zmienić) - są szanse, że będziesz lepszy z sortowaniem po scaleniu. W przypadku prostszych zadań szybkie sortowanie będzie szybsze.

To powiedziane, że wszystko, co wcześniej powiedziano, jest prawdą: - Quicksort może być N ^ 2, ale Sedgewick twierdzi, że dobra randomizowana implementacja ma większe szanse, że komputer wykonujący rodzaj zostanie uderzony piorunem, niż pójdzie N ^ 2 - Mergesort wymaga dodatkowej przestrzeni

Kiedy eksperymentowałem z obydwoma algorytmami sortowania, licząc liczbę wywołań rekurencyjnych, Quicksort konsekwentnie ma mniej wywołań rekurencyjnych niż scalanie. Wynika to z faktu, że quicksort ma pivots, a pivots nie są uwzględniane w następnych wywołaniach rekurencyjnych. W ten sposób quicksort może szybciej dotrzeć do bazowej rekurencyjnej bazy danych niż scalanie.

Jest to częste pytanie zadawane w wywiadach, że pomimo lepszych wyników w najgorszym przypadku sortowania przez scalanie, szybkie sortowanie jest uważane za lepsze niż sortowanie przez scalanie, szczególnie w przypadku dużego wkładu. Istnieją pewne powody, dla których Quicksort jest lepszy:

1- Przestrzeń pomocnicza: Szybkie sortowanie to algorytm sortowania na miejscu. Sortowanie na miejscu oznacza, że ​​do przeprowadzenia sortowania nie jest wymagana dodatkowa przestrzeń dyskowa. Z drugiej strony Scal sortowanie wymaga tymczasowej tablicy do scalenia posortowanych tablic, a zatem nie jest na miejscu.

2 - Najgorszy przypadek: najgorszego przypadku szybkiego sortowania O(n^2)można uniknąć, używając losowego szybkiego sortowania. Można go łatwo uniknąć z dużym prawdopodobieństwem, wybierając odpowiedni punkt obrotu. Uzyskanie przeciętnego zachowania przypadku przez wybranie odpowiedniego elementu przestawnego powoduje, że poprawia ono wydajność i staje się tak samo wydajne, jak sortowanie scalone.

3- Lokalizacja odniesienia: W szczególności Quicksort wykazuje dobrą lokalizację pamięci podręcznej, co sprawia, że ​​jest szybsza niż sortowanie scalone w wielu przypadkach, np. W środowisku pamięci wirtualnej.

4- Rekurencja na ogonie: QuickSort jest rekurencyjny na ogonie, podczas gdy sortowanie scalające nie. Funkcja rekurencyjna tail jest funkcją, w której wywołanie rekurencyjne jest ostatnią rzeczą wykonywaną przez funkcję. Funkcje rekurencyjne są traktowane lepiej niż funkcje rekurencyjne, ponieważ rekurencja może być zoptymalizowana przez kompilator.

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ż scalanie, tylko dlatego, że łatwiej jest zakodować ścisłą implementację, a wykonywane operacje mogą przebiegać szybciej. Wynika to z faktu, że Quicksort jest generalnie szybszy, że ludzie używają go zamiast scalania.

Jednak! Ja osobiście często używam scalesort lub wariantu quicksort, który degraduje się do scalesort, gdy quicksort robi to źle. Zapamiętaj. Quicksort tylko O (n log n) na średni . Najgorszym przypadkiem jest O (n ^ 2)! Mergesort ma zawsze wartość O (n log n). W przypadkach, gdy wydajność lub czas reakcji w czasie rzeczywistym jest koniecznością, a dane wejściowe mogą pochodzić ze złośliwego źródła, nie powinieneś używać zwykłego szybkiego sortowania.

Gdy wszystko jest takie samo, spodziewałbym się, że większość ludzi będzie korzystać z tego, co jest najwygodniej dostępne, a jest to zwykle qsort (3). Poza tym wiadomo, że szybkie sortowanie tablic jest bardzo szybkie, podobnie jak scalesort jest powszechnym wyborem dla list.

Co Zastanawiam się, dlaczego tak rzadko zdarza się zobaczyć przelicznika lub sortowanie kubełkowe. Są to O (n), przynajmniej na połączonych listach, a wystarczy jakaś metoda konwersji klucza na liczbę porządkową. (łańcuchy i zmiennoprzecinkowe działają dobrze.)

Myślę, że powód ma związek z nauczaniem informatyki. Musiałem nawet wykazać mojemu wykładowcowi w analizie algorytmu, że rzeczywiście możliwe było sortowanie szybciej niż O (n log (n)). (Miał dowód, że porównania nie można sortować szybciej niż O (n log (n)), co jest prawdą.)

W innych wiadomościach liczby zmiennoprzecinkowe można sortować jako liczby całkowite, ale później trzeba obrócić liczby ujemne.

Edycja: Właściwie to jeszcze bardziej błędny sposób sortowania liczb zmiennoprzecinkowych: http://www.stereopsis.com/radix.html . Pamiętaj, że sztuczki polegającej na przerzucaniu bitów można używać niezależnie od tego, jakiego algorytmu sortowania faktycznie używasz ...

Małe dodatki do sortowania szybkiego vs scalania.

Może to również zależeć od rodzaju sortowania przedmiotów. Jeśli dostęp do pozycji, zamiana i porównania nie są prostymi operacjami, takimi jak porównywanie liczb całkowitych w pamięci płaszczyzny, algorytm scalania może być preferowanym algorytmem.

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

Ponadto w niestandardowych kontenerach, takich jak „lista połączona”, nie ma zalet szybkiego sortowania.
1. Scal sortuj na połączonej liście, nie potrzebujesz dodatkowej pamięci. 2. Dostęp do elementów w szybkim sortowaniu nie jest sekwencyjny (w pamięci)

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

W przeciwieństwie do tablic, na liście polubionych możemy wstawiać elementy pośrodku ze spacją O (1) i czasem O (1), dlatego operacja scalania w sortowaniu scalającym może być realizowana bez dodatkowej spacji. Jednak przydzielanie i zwalnianie dodatkowej przestrzeni dla tablic ma negatywny wpływ na czas działania sortowania scalającego. Sortowanie korespondencji faworyzuje również listę połączoną, ponieważ dane są uzyskiwane sekwencyjnie, bez większego losowego dostępu do pamięci.

Z drugiej strony szybkie sortowanie wymaga dużo losowego dostępu do pamięci, a dzięki tablicy możemy bezpośrednio uzyskać dostęp do pamięci bez przechodzenia zgodnie z wymaganiami połączonych list. Również szybkie sortowanie w przypadku tablic ma dobrą lokalizację odniesienia, ponieważ tablice są przechowywane w pamięci w sposób ciągły.

Chociaż średnia złożoność obu algorytmów sortowania wynosi O (NlogN), zwykle osoby wykonujące zwykłe zadania używają tablicy do przechowywania danych, dlatego też algorytmem szybkim powinno być sortowanie szybkie.

EDYCJA: Właśnie dowiedziałem się, że łączenie sortowania najgorszy / najlepszy / średni przypadek to zawsze nlogn, ale szybkie sortowanie może różnić się od n2 (najgorszy przypadek, gdy elementy są już posortowane) do nlogn (średni / najlepszy przypadek, gdy oś przestawna zawsze dzieli tablicę na dwie części połówki).

Weź pod uwagę złożoność czasu i przestrzeni. Dla sortowania scalonego: Złożoność czasowa: O (nlogn), Złożoność przestrzeni: O (nlogn)

Do szybkiego sortowania: Złożoność czasu: O (n ^ 2), Złożoność przestrzeni: O (n)

Teraz oboje wygrywają w jednym scenariuszu. Ale za pomocą losowego obrotu można prawie zawsze zmniejszyć złożoność czasową szybkiego sortowania do O (nlogn).

Dlatego w wielu aplikacjach preferowane jest Szybkie sortowanie zamiast Sortuj.

W środowisku c / c ++, gdy nie używam kontenerów stl, zwykle używam quicksort, ponieważ jest on wbudowany w czas wykonywania, podczas gdy scalesort nie.

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

Ponadto wydajność może być znacznie wyższa przy szybkim sortowaniu, w przypadkach, gdy cały zestaw danych nie mieści się w zestawie roboczym.

Jednym z powodów jest bardziej filozoficzny. Quicksort to filozofia Top-> Down. Przy n elementach do sortowania jest n! możliwości. Dzięki 2 wzajemnie wykluczającym się podziałom m & nm liczba możliwości spada o kilka rzędów wielkości. m! * (nm)! 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 ekstrapoluj do 1 miliona silni w stosunku do 900 000! * 100 000! vs. Więc zamiast martwić się o ustanowienie jakiegokolwiek porządku w zakresie lub partycji, po prostu ustal porządek na szerszym poziomie w partycjach i zmniejsz możliwości w obrębie partycji. Wszelkie zamówienia ustalone wcześniej w obrębie zakresu zostaną później zakłócone, jeśli same partycje nie wykluczają się wzajemnie.

Każde podejście oddolne, takie jak sortowanie scalone lub sortowanie stosów, przypomina podejście pracownika lub pracownika, w którym wcześnie zaczyna się porównywanie na poziomie mikroskopowym. Ale ta kolejność musi zostać utracona, gdy tylko element między nimi zostanie znaleziony później. Podejścia te są bardzo stabilne i wyjątkowo przewidywalne, ale wykonują pewną dodatkową pracę.

Szybkie sortowanie przypomina podejście kierownicze, w którym początkowo nie ma obawy o jakiekolwiek zamówienie, a jedynie o spełnienie szerokiego kryterium Bez względu na zamówienie. Następnie partycje są zawężane, aż pojawi się posortowany zestaw. Prawdziwym wyzwaniem w Quicksort jest znalezienie partycji lub kryterium w ciemności, gdy nie wiesz nic o sortowaniu elementów. Dlatego musimy albo podjąć wysiłek, aby znaleźć medianę wartości, albo wybrać 1 losowo, albo zastosować dowolne podejście „kierownicze”. Znalezienie idealnej mediany może wymagać znacznego wysiłku i znów prowadzi do głupiego podejścia oddolnego. Tak więc Quicksort mówi, że wystarczy wybrać losowy punkt obrotu i mieć nadzieję, że znajdzie się gdzieś pośrodku lub wykona pracę, aby znaleźć medianę 3, 5 lub coś więcej, aby znaleźć lepszą medianę, ale nie planuj być idealny i nie t marnować czas przy początkowym zamawianiu. Wydaje się, że dobrze to robi, jeśli masz szczęście lub czasem spadasz do n ^ 2, gdy nie dostajesz mediany, ale po prostu zaryzykujesz. W dowolny sposób dane są losowe. dobrze. Zgadzam się więc bardziej z logicznym podejściem Quicksort u góry -> w dół i okazuje się, że szansa, jaką zajmuje przy wyborze osi obrotu i porównaniach, które wcześniej zapisuje, wydaje się działać lepiej niż jakikolwiek drobiazgowy i dokładny stabilny dno -> podejście do góry jak scalanie sortuj. Ale porównania, które wcześniej zapisuje, wydają się działać lepiej niż jakakolwiek drobiazgowa i dokładna stabilna metoda bottom -> up jak sortowanie scalone. Ale porównania, które wcześniej zapisuje, wydają się działać lepiej niż jakakolwiek drobiazgowa i dokładna stabilna metoda bottom -> up jak sortowanie scalone. Ale