Dlaczego Quicksort jest lepszy od FusionSort?


354

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


91
To nie jest bardzo dobre pytanie podczas rozmowy kwalifikacyjnej. Rzeczywiste dane nie są tasowane: często zawierają dużo porządku, z którego może korzystać inteligentny sort, i chociaż żaden algorytm nie robi tego automatycznie, łatwiej jest zhakować sortowanie scalające, aby to zrobić niż szybki. GNU libc qsort, Python list.sorti Array.prototype.sortJavaScript w Firefoksie są przerobionymi rodzajami scalania. (GNU STL sortzamiast tego korzysta z Introsort, ale może to być spowodowane tym, że w C ++ zamiana potencjalnie wygrywa z kopiowaniem.)
Jason Orendorff,

3
@Jason Orendorff: Dlaczego tak jest "easier to hack a mergesort to do it than a quicksort"? Jakiś konkretny przykład, który możesz zacytować?
Lazer,

16
@eSKay Sortowanie scalające rozpoczyna się od zgrupowania początkowych danych w posortowane podgrupy. Jeśli tablica początkowo zawiera niektóre już posortowane regiony, możesz zaoszczędzić dużo czasu, wykrywając, że znajdują się tam przed rozpoczęciem. I możesz to zrobić w czasie O (n). Aby zapoznać się z konkretnymi przykładami, zobacz kod źródłowy trzech wspomnianych projektów! Najlepszym przykładem może być Pythona Timsort opisane szczegółowo tutaj: svn.python.org/view/python/trunk/Objects/... i realizowane w svn.python.org/view/python/trunk/Objects/... .
Jason Orendorff,

4
@JasonOrendorff: Nie jestem pewien, czy kupuję twój argument, że scalanie można łatwiej zmodyfikować, aby skorzystać z już posortowanych sekcji. Etap partycjonowania Quicksort można w prosty sposób zmodyfikować, aby następnie sprawdzić, czy obie wynikowe partycje są posortowane, i zatrzymać rekurencję, jeśli tak jest. To potencjalnie podwaja liczbę porównań, ale nie zmienia złożoności czasowej O (n) tego kroku.
j_random_hacker

3
@j_random_hacker: tak, właśnie to sugerowałem. Ale zastanów się: {10, 2, 3, 4, 5, 6, 7, 8, 1, 9} Pomimo tego, że są już prawie całkowicie posortowane, sprawdzanie przed partycją go nie znajdzie, ani później. Partycja spieprzy to, zanim sprawdzą ją kolejne połączenia. Tymczasem sprawdzanie sortowania przez scalanie sprawdza posortowane sekwencje w krokach podziału, zanim zostaną one przeniesione, a inteligentne będą szukać takich przebiegów właśnie podczas kroku podziału (patrz: Tim Sort)
Kaczka Mooing

Odpowiedzi:


275

Quicksort ma czas działania w najgorszym przypadku O ( n 2 ) 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 2 ), 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 .


4
Artykuł w Wikipedii mówi, że zmienia się w heapsort, a nie w scalanie ... tylko dla twojej informacji.
Sev

3
@Sev:… podobnie jak papier orignal. Dzięki za zwrócenie uwagi na błąd. - Nie, że to naprawdę ma znaczenie, ponieważ ich asymptotyczny czas działania jest taki sam.
Konrad Rudolph,

110
dlaczego wybrano to jako poprawną odpowiedź? Wszystko, co wyjaśnia, to jak łatane są problemy z szybkim sortowaniem. Nadal nie wiadomo, dlaczego szybkie sortowanie jest używane bardziej niż inne? Czy odpowiedź „szybkie sortowanie jest używana bardziej niż inna, ponieważ po jednej głębokości możesz przełączyć się na rozsypisko”? .. dlaczego więc nie skorzystać z heapsortu? .. po prostu próbuję zrozumieć ...
codeObserver

16
@ p1 Dobre pytanie. Rzeczywista odpowiedź jest taka, że ​​średnio w przypadku średnich danych szybkie sortowanie jest szybsze niż sortowanie scalone (i sortowanie sterty, jeśli chodzi o to), i chociaż najgorszy przypadek szybkiego sortowania jest wolniejszy niż sortowanie scalone, ten najgorszy przypadek można bardzo łatwo złagodzić (stąd moja odpowiedź).
Konrad Rudolph

4
Quicksort jest również lepszy pod względem pamięci.
Shashwat

287

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.


1
Bardzo miło, nie pomyślałem o założeniach dotyczących dostępu do struktury danych. Dobry wgląd :)
chutsu

2
Czy możesz wyjaśnić, co rozumiesz przez „poszukiwanie na dysk”, czy oznacza to poszukiwanie jakiejś pojedynczej wartości, gdy dane są przechowywane na dysku?
James Wierzba,

8
@JamesWierzba Biorę z kontekstu, że ma na myśli „szukanie lokalizacji na dysku”. „Wyszukiwanie” na obracającym się urządzeniu dyskowym oznacza podniesienie głowicy czytającej i przeniesienie jej na nowy adres bezwzględny, co jest niezwykle powolną operacją. Gdy uzyskujesz dostęp do danych w kolejności, w jakiej zostały zapisane, sprzęt dyskowy nie musi szukać, po prostu leci z dużą prędkością, odczytując kolejno elementy.
nclark

1
Czy ktoś może to trochę wyjaśnić? Tak to widzę: Quicksort: Jeśli wybieramy losowy element przestawny, stos wywołań ma fragmenty tablicy podzielone na części w losowy sposób. Wymaga to losowego dostępu. Jednak dla każdego wywołania w stosie zarówno lewy, jak i prawy wskaźnik poruszają się sekwencyjnie. Zakładam, że będą one przechowywane w pamięci podręcznej. Zamiany są ponownie operacjami na informacjach znajdujących się w pamięci podręcznej (i ostatecznie zapisanych na dysku). (ciąg dalszy w moim następnym komentarzu)
sam

1
Tylko wkład w uniknięcie kosztownego obciążenia odczytu / zapisu dysku : Podczas sortowania bardzo dużych danych, które wymagają dostępu do dysku, korzystne jest zmienianie kierunku sortowania dla każdego przejścia. Oznacza to, że na bardzo najwyższym poziomie pętli, raz idziesz od 0kierunku ni następnym razem pójdziesz od nkierunku 0. Ma to tę zaletę, że wycofuje (sortuje) bloki danych, które są już dostępne w pamięci (pamięci podręcznej) i atakuje dwukrotnie tylko dla jednego dostępu do dysku. Myślę, że większość DBMS używa tej techniki optymalizacji.
ssd

89

W rzeczywistości QuickSort to O (n 2 ). Jego przeciętna sprawa czas trwania wynosi O (nlog (n)), ale jego najgorszym przypadku wynosi O (n 2 ), 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łą.

4
W rzeczywistości istnieją implementacje QuickSort, które w najgorszym przypadku to O (n * log (n)), a nie O (n ^ 2).
jfs

12
Zależy to również od architektury komputera. Quicksort korzysta z pamięci podręcznej, a MergeSort nie.
Cristian Ciupitu,

4
@JF Sebastian: Najprawdopodobniej są to implementacje introsortu, a nie quicksort (introsort zaczyna się jako quicksort i przełącza się na heapsort, jeśli ma przestać być n * log (n)).
CesarB,

44
Możesz zaimplementować scalanie na miejscu.
Marcin,

6
Sortowanie korespondencji seryjnej może być zaimplementowane w sposób, który wymaga tylko dodatkowej pamięci O (1), ale większość z tych implementacji bardzo cierpi z powodu wydajności.
Jaśniejsze

29

„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”.


3
Nie odpowiada na pytanie, co jest lepsze. Nazwa algorytmu nie ma znaczenia przy określaniu, który jest lepszy.
Nick Gallimore

18

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.


9

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 .


7

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


7

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


Mergesort można wdrożyć na miejscu, tak aby nie wymagał dodatkowej przestrzeni. Na przykład z podwójnie połączoną listą: stackoverflow.com/questions/2938495/…
lanoxx

6

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.


5

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.


Najgorszym przypadkiem quicksort jest O (n), scalesort O (n log n) - więc jest tam duża różnica.
paul23

1
w najgorszym przypadku quicksort to O (n ^ 2) - nie mogę edytować mojego poprzedniego komentarza i
napisałem

@ paul23 komentarze można usunąć. Ponadto odpowiedź już dotyczyła twojego punktu: „w większości danych rzeczywistych można dokonywać wyborów projektowych, które minimalizują prawdopodobieństwo wymagania czasu kwadratowego”
Jim Balter,

5

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


1
„istniejące świetne odpowiedzi” - jakie to są? Nie mogę ich zlokalizować.
Jim Balter

Czy jakieś odmiany Szybkiego sortowania powiadamiają funkcję porównywania o partycjach w taki sposób, który pozwoliłby jej wykorzystać sytuacje, w których znaczna część klucza będzie taka sama dla wszystkich elementów w partycji?
supercat

4

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


„Można to złagodzić przez losowe odtwarzanie losowe przed rozpoczęciem sortowania.” - Eee, nie, to byłoby drogie. Zamiast tego użyj losowych osi.
Jim Balter

4

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.


2
Drugie zdanie mówi: „... scalesort jest potencjalnie znacznie wolniejszy niż… scalesort”. Pierwszym odniesieniem powinno być prawdopodobnie szybkie sortowanie.
Jonathan Leffler

Sortowanie po scaleniu jest stabilne tylko wtedy, gdy algorytm scalania jest stabilny; nie jest to gwarantowane.
Jaśniejsze

@ Wyczyść Jest to gwarantowane, jeśli <=jest używane do porównań <, a nie ma powodu, aby tego nie robić .
Jim Balter

@JimBalter Mógłbym z łatwością wymyślić niestabilny algorytm scalania (na przykład ta funkcja mogłaby pełnić tę funkcję). Powodem, dla którego szybkie sortowanie jest szybsze niż sortowanie scalone w wielu przypadkach, nie jest to spowodowane zmniejszonym narzutem, ale tym, w jaki sposób quicksort uzyskuje dostęp do danych, co jest o wiele bardziej przyjazne dla pamięci podręcznej niż standardowy tryb scalania.
Jaśniejsze

@Clearer quicksort nie jest sortowaniem według scalenia ... twoje oświadczenie z 21 grudnia 2014 r., Na które odpowiedziałem, dotyczyło wyłącznie sortowania scalającego i tego, czy jest stabilne. quicksort, który jest szybszy, nie ma żadnego związku z twoim komentarzem lub moją odpowiedzią. Koniec dyskusji dla mnie ... w kółko.
Jim Balter,

3

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


3

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.


To, że oś nie jest częścią tego rodzaju na następnym poziomie, nie jest powodem, dla którego QS jest bardziej wydajna. Zobacz inne odpowiedzi, aby uzyskać dodatkowe informacje.
Jim Balter

@JimBalter Do jakich „innych odpowiedzi” masz na myśli? Najlepsza odpowiedź mówi tylko, że QS „wymaga niewiele dodatkowej przestrzeni i wykazuje dobrą lokalizację pamięci podręcznej”, ale nie wyjaśnia, dlaczego tak jest, ani nie podaje żadnych cytatów. Druga odpowiedź mówi po prostu, że sortowanie według scalania jest lepsze dla większych zestawów danych
RvPr

Przesuwasz bramki, od tego, dlaczego QS jest bardziej wydajny, do wyjaśniania podstawowych faktów na temat jego działania. Zrobią to odpowiedzi na inne pytania: stackoverflow.com/questions/9444714/ ... ... Mam nadzieję, że to ci wystarczy; Nie odpowiem więcej.
Jim Balter

3

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.


Nie, najgorszy przypadek QuickSort nie występuje, gdy tablica jest już posortowana, chyba że użyjesz pierwszego lub ostatniego elementu jako elementu przestawnego, ale nikt tego nie robi.
Jim Balter

2

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.


2
W jaki sposób Quicksort ma lepszą średnią złożoność spraw? Oba są O (nlgn). Twierdziłbym, że atakujący nie dostarczy danych wejściowych do żadnego algorytmu sortowania ... ale w interesie nieprzyjmowania bezpieczeństwa przez zaciemnienie, załóżmy, że mógłby. Chociaż czas działania n ^ 2 jest gorszy niż nlgn, nie jest wystarczająco gorsze, że serwer WWW ulegnie awarii w wyniku pojedynczego ataku. W rzeczywistości argument DOS jest prawie zerowy, ponieważ każdy serwer WWW jest podatny na atak DDOS, i jest bardziej prawdopodobne, że atakujący użyje rozproszonej sieci hostów, wszystko zalewa TCP SYN.
CaTalyst.X

„Quicksort ma lepszą średnią złożoność spraw” - nie, nie ma.
Jim Balter

2

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.


2

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.


O (2n) == O (n). Prawidłowe stwierdzenie jest takie, że Mergesort potrzebuje O (n) dodatkowej pamięci (dokładniej, potrzebuje n / 2 pamięci pomocniczej). I nie dotyczy to list połączonych.
Jim Balter

@JimBalter Sir, czy mógłbyś podzielić się z nami swoimi genialnymi i wartościowymi pomysłami na temat ich występów jako odpowiedzią na pytanie? Z góry dziękuję.
snr

2

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


Czy qsort bije scalanie nawet dla posortowanych danych wejściowych, jeśli porównanie jest tanie?
Eonil

2

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.


Pivots nie mają nic wspólnego z tym, dlaczego QS ma mniej połączeń rekurencyjnych ... to dlatego, że połowa rekurencji QS to rekurencja ogona, którą można wyeliminować.
Jim Balter

2

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.


1

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.


1

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


1
Widziałem moją część rodzajów radix. Ale jest dość trudny w użyciu, ponieważ jeśli zostanie poprawnie przeanalizowany, jego środowisko wykonawcze nie jest równe O (n), ponieważ zależy od więcej niż liczby elementów wejściowych. Ogólnie rzecz biorąc, bardzo trudno jest przewidzieć tego rodzaju silne przewidywania, że ​​sortowanie radix musi być skuteczne w odniesieniu do danych wejściowych.
Konrad Rudolph,

Jest to O (n), gdzie n jest całkowitym rozmiarem wejściowym, tzn. Łącznie z rozmiarem elementów. To prawda, że ​​możesz to zaimplementować, więc musisz uzupełnić dużą liczbą zer, ale używanie słabej implementacji do porównania jest nonsensowne. (To powiedziawszy, wdrożenie może być trudne, ymmv.)
Anders Eurenius,

Zauważ, że jeśli używasz GNU libc, qsortto sortowanie według scalania.
Jason Orendorff,

Mówiąc dokładniej, jest to rodzaj scalania, chyba że nie można przydzielić niezbędnej pamięci tymczasowej. cvs.savannah.gnu.org/viewvc/libc/stdlib/…
Jason Orendorff,

1

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)


0

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


0

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.


-1

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.


3
W rzeczywistości, jeśli mówimy o funkcji bibliotecznej qsort (), może ona być lub nie być zaimplementowana jako quicksort.
Thomas Padron-McCarthy

3
Konrad, przepraszam, że jestem trochę analny na ten temat, ale skąd ta gwarancja? Nie mogę go znaleźć w standardzie ISO C ani w standardzie C ++.
Thomas Padron-McCarthy

2
GNU libc qsortjest rodzajem scalania, chyba że liczba elementów jest naprawdę gigantyczna lub nie można przydzielić pamięci tymczasowej. cvs.savannah.gnu.org/viewvc/libc/stdlib/…
Jason Orendorff,

-3

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


quicksort korzysta z losowości wyboru osi przestawnej. Losowy punkt obrotu miałby naturalnie tendencję do podziału 50:50 i jest mało prawdopodobne, aby był konsekwentny w kierunku jednej z ekstremów. Stały współczynnik nlogn jest dość niski, aż średni podział wynosi 60-40, a nawet 70-30.
Winter Melon

To kompletny nonsens. quicksort jest używany ze względu na jego działanie, a nie „filozofię” ... a twierdzenia o „porządku zostaną utracone” są po prostu fałszywe.
Jim Balter
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.