Quicksort vs heapsort


Odpowiedzi:


61

Ten artykuł zawiera analizę.

Również z Wikipedii:

Najbardziej bezpośrednim konkurentem quicksort jest heapsort. Heapsort jest zwykle nieco wolniejszy niż quicksort, ale w najgorszym przypadku czas wykonywania wynosi zawsze Θ (nlogn). Szybkie sortowanie jest zwykle szybsze, chociaż istnieje szansa na wydajność w najgorszym przypadku, z wyjątkiem wariantu introsort, który przełącza się na heapsort, gdy zostanie wykryty zły przypadek. Jeśli z góry wiadomo, że port sterty będzie konieczny, użycie go bezpośrednio będzie szybsze niż czekanie, aż introsort się do niego przełączy.


12
Warto zauważyć, że w typowych implementacjach ani quicksort, ani heapsort nie są sortami stabilnymi.
MjrKusanagi

@DVK, Według twojego linku cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html , sortowanie na stosie wymaga 2842 porównań dla n = 100, ale dla n = 500 wymaga 53113 porównań. A to implikuje, że stosunek między n = 500 a n = 100 jest 18 razy i NIE pasuje do algorytmu sortowania sterty ze złożonością O (N logN). Wydaje mi się, że jest całkiem prawdopodobne, że ich implementacja sortowania sterty zawiera jakieś błędy.
DU Jiaen,

@DUJiaen - pamiętaj, że O () dotyczy asymptotycznego zachowania przy dużym N i ma możliwy mnożnik
DVK

NIE jest to związane z mnożnikiem. Jeśli algorytm ma złożoność O (N log N), powinien być zgodny z trendem Czas (N) = C1 * N * log (N). A jeśli weźmiesz Czas (500) / Czas (100), oczywiste jest, że C1 zniknie, a wynik powinien być zamknięty do (500 log500) / (100 log100) = 6,7. Ale z twojego linku jest 18, czyli zbyt daleko poza skalą.
DU Jiaen,

2
Link nie działa
PlsWork

127

Heapsort jest gwarantowany przez O (N log N), co jest znacznie lepsze niż najgorszy przypadek w Quicksort. Heapsort nie potrzebuje więcej pamięci dla innej tablicy do umieszczania uporządkowanych danych, tak jak jest to wymagane przez Mergesort. Dlaczego więc komercyjne aplikacje trzymają się Quicksort? Co Quicksort wyróżnia się spośród innych implementacji?

Sam przetestowałem algorytmy i zauważyłem, że Quicksort ma naprawdę coś specjalnego. Działa szybko, znacznie szybciej niż algorytmy Heap and Merge.

Sekret Quicksort polega na tym, że prawie nie wykonuje niepotrzebnych zamian elementów. Zamiana jest czasochłonna.

Dzięki Heapsort, nawet jeśli wszystkie twoje dane są już uporządkowane, zamierzasz zamienić 100% elementów, aby zamówić tablicę.

Z Mergesort jest jeszcze gorzej. Zamierzasz zapisać 100% elementów w innej tablicy i zapisać ją z powrotem w oryginalnej, nawet jeśli dane są już uporządkowane.

Dzięki Quicksort nie zamieniasz tego, co już zostało zamówione. Jeśli Twoje dane są całkowicie uporządkowane, prawie nic nie wymieniasz! Chociaż jest dużo zamieszania na temat najgorszego przypadku, niewielka poprawa wyboru przestawienia, inna niż uzyskanie pierwszego lub ostatniego elementu tablicy, może tego uniknąć. Jeśli uzyskasz trzpień z elementu pośredniego między pierwszym, ostatnim i środkowym elementem, wystarczy uniknąć najgorszego przypadku.

To, co jest lepsze w Quicksort, nie jest najgorszym przypadkiem, ale najlepszym! W najlepszym przypadku wykonujesz tę samą liczbę porównań, ok, ale prawie nic nie zamieniasz. W przeciętnym przypadku wymieniasz część elementów, ale nie wszystkie, jak w Heapsort i Mergesort. To właśnie zapewnia Quicksort najlepszy czas. Mniej wymiany, większa prędkość.

Poniższa implementacja w C # na moim komputerze, działająca w trybie zwolnienia, pokonuje Array.Sort o 3 sekundy ze środkowym przestawieniem i o 2 sekundy z ulepszonym obrotem (tak, jest narzut, aby uzyskać dobry obrót).

static void Main(string[] args)
{
    int[] arrToSort = new int[100000000];
    var r = new Random();
    for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);

    Console.WriteLine("Press q to quick sort, s to Array.Sort");
    while (true)
    {
        var k = Console.ReadKey(true);
        if (k.KeyChar == 'q')
        {
            // quick sort
            Console.WriteLine("Beg quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            QuickSort(arrToSort, 0, arrToSort.Length - 1);
            Console.WriteLine("End quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
        else if (k.KeyChar == 's')
        {
            Console.WriteLine("Beg Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            Array.Sort(arrToSort);
            Console.WriteLine("End Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
    }
}

static public void QuickSort(int[] arr, int left, int right)
{
    int begin = left
        , end = right
        , pivot
        // get middle element pivot
        //= arr[(left + right) / 2]
        ;

    //improved pivot
    int middle = (left + right) / 2;
    int
        LM = arr[left].CompareTo(arr[middle])
        , MR = arr[middle].CompareTo(arr[right])
        , LR = arr[left].CompareTo(arr[right])
        ;
    if (-1 * LM == LR)
        pivot = arr[left];
    else
        if (MR == -1 * LR)
            pivot = arr[right];
        else
            pivot = arr[middle];
    do
    {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;

        if(left <= right)
        {
            int temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;

            left++;
            right--;
        }
    } while (left <= right);

    if (left < end) QuickSort(arr, left, end);
    if (begin < right) QuickSort(arr, begin, right);
}

10
+1 do rozważań na temat nr. wymiany, operacje odczytu / zapisu wymagane dla różnych algorytmów sortowania
ycy

2
W przypadku dowolnej deterministycznej strategii wyboru obrotu w czasie stałym można znaleźć tablicę, która daje O (n ^ 2) najgorszy przypadek. Nie wystarczy wyeliminować tylko minimum. Musisz niezawodnie wybierać pivoty, które znajdują się w określonym przedziale.
Antymon

1
Jestem ciekawy, czy to jest dokładny kod, który uruchomiłeś dla swoich symulacji między ręcznie zakodowanym szybkim sortowaniem a wbudowanym w C # Array.sort? Przetestowałem ten kod i we wszystkich moich testach w najlepszym przypadku ręcznie kodowane szybkie sortowanie było takie samo jak Array.sort. Jedną z rzeczy, na które zwracałem uwagę podczas moich testów, było wykonanie dwóch identycznych kopii losowej tablicy. W końcu dana randomizacja mogłaby być potencjalnie bardziej korzystna (skłaniać się ku najlepszym przypadkom) niż inna randomizacja. Więc przeprowadziłem identyczne zestawy dla każdego z nich. Array.sort remisuje lub bije za każdym razem (kompilacja wydania btw).
Chris,

1
Sortowanie przez scalanie nie musi kopiować 100% elementów, chyba że jest to jakaś bardzo naiwna implementacja z podręcznika. Jest to proste do zaimplementowania, dzięki czemu wystarczy skopiować tylko 50% z nich (lewa strona dwóch scalonych tablic). Odkładanie kopiowania jest również trywialne, dopóki nie będziesz musiał faktycznie "zamienić" dwóch elementów, więc z już posortowanymi danymi nie będziesz mieć narzutu pamięci. Więc nawet 50% jest w rzeczywistości najgorszym przypadkiem i możesz mieć wszystko między tym a 0%.
ddekany,

1
@MarquinhoPeli Chciałem powiedzieć, że potrzebujesz tylko 50% więcej dostępnej pamięci w porównaniu do rozmiaru posortowanej listy, a nie 100%, co wydaje się być powszechnym nieporozumieniem. Więc mówiłem o maksymalnym zużyciu pamięci. Nie mogę podać linku, ale łatwo jest zobaczyć, jeśli spróbujesz scalić dwie już posortowane połówki tablicy na miejscu (tylko lewa połowa ma problem polegający na nadpisywaniu elementów, których jeszcze nie wykorzystałeś). To, ile pamięci musisz skopiować podczas całego procesu sortowania, to inna kwestia, ale oczywiście w najgorszym przypadku nie może być poniżej 100% dla dowolnego algorytmu sortowania.
ddekany

15

W większości sytuacji posiadanie szybkiego lub trochę szybszego jest nieistotne ... po prostu nigdy nie chcesz, aby od czasu do czasu było bardzo wolno. Chociaż możesz dostosować QuickSort, aby uniknąć powolnych sytuacji, tracisz elegancję podstawowego QuickSort. Tak więc w przypadku większości rzeczy wolę HeapSort ... możesz zaimplementować go w pełnej prostej elegancji i nigdy nie uzyskać powolnego sortowania.

W sytuacjach, w których W większości przypadków NIE zależy Ci na maksymalnej prędkości, QuickSort może być preferowany zamiast HeapSort, ale żadne z nich nie może być właściwą odpowiedzią. W sytuacjach krytycznych dla prędkości warto dokładnie przyjrzeć się szczegółom sytuacji. Na przykład w niektórych moich kodach krytycznych dla szybkości bardzo często dane są już posortowane lub prawie posortowane (jest to indeksowanie wielu powiązanych pól, które często poruszają się w górę iw dół razem lub przesuwają się w górę iw dół naprzeciw siebie, więc gdy posortujesz według jednego, pozostałe są sortowane, sortowane odwrotnie lub zamykane ... z których każdy może zabić QuickSort). W tym przypadku nie zaimplementowałem ani ... zamiast tego zaimplementowałem Dijkstra's SmoothSort ... wariant HeapSort, który jest O (N), gdy jest już posortowany lub prawie posortowany ... nie jest tak elegancki, niezbyt łatwy do zrozumienia, ale szybko ... czytajhttp://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF, jeśli chcesz czegoś trudniejszego w kodzie.


6

Lokalne hybrydy Quicksort-Heapsort są również bardzo interesujące, ponieważ większość z nich wymaga tylko n * log n porównań w najgorszym przypadku (są optymalne w odniesieniu do pierwszego członu asymptotyki, więc unikają najgorszych scenariuszy of Quicksort), O (log n) extra space i zachowują co najmniej „połowę” dobrego zachowania Quicksort w odniesieniu do już uporządkowanego zbioru danych. Niezwykle ciekawy algorytm zaprezentowali Dikert i Weiss w http://arxiv.org/pdf/1209.4214v1.pdf :

  • Wybierz pivot p jako medianę losowej próbki elementów sqrt (n) (można to zrobić w maksymalnie 24 porównaniach sqrt (n) za pomocą algorytmu Tarjan & co lub 5 porównań sqrt (n) za pomocą znacznie bardziej zawiłego pająka -fabryczny algorytm Schonhage);
  • Podziel tablicę na dwie części, tak jak w pierwszym kroku Quicksort;
  • Zbierz najmniejszą część i użyj O (log n) dodatkowych bitów, aby zakodować stertę, w której każde lewe dziecko ma wartość większą niż jego rodzeństwo;
  • Rekurencyjnie wyodrębnij korzeń pryzmy, przesiej szparę pozostawioną przez korzeń, aż dojdzie do liścia pryzmy, a następnie wypełnij szparę odpowiednim elementem pobranym z drugiej części szyku;
  • Powtarzaj w pozostałej nieuporządkowanej części tablicy (jeśli jako dokładną medianę wybrano p, rekursja w ogóle nie występuje).

2

Comp. między quick sorti merge sortponieważ oba są typem sortowania w miejscu, istnieje różnica między czasem wykonywania operacji wrost a czasem wykonywania operacji wrost dla szybkiego sortowania wynosi O(n^2)i dla sortowania na stosie nadalO(n*log(n)) i dla średniej ilości danych szybkie sortowanie będzie bardziej przydatne. Ponieważ jest to algorytm losowy, więc prawdopodobieństwo uzyskania poprawnych odpowiedzi. w krótszym czasie będzie zależeć od pozycji wybranego elementu obrotowego.

Więc a

Dobra decyzja: każdy rozmiar L i G jest mniejszy niż 3s / 4

Pomyłka: jeden z L i G ma rozmiar większy niż 3s / 4

dla małej ilości możemy przejść do sortowania przez wstawianie, a dla bardzo dużej ilości danych do sortowania na stosie.


Chociaż sortowanie przez scalanie można zaimplementować za pomocą sortowania w miejscu, implementacja jest złożona. AFAIK, większość implementacji sortowania przez scalanie nie jest na miejscu, ale są stabilne.
MjrKusanagi

2

Heapsort ma tę zaletę, że ma najgorszy działający przypadek O (n * log (n)), więc w przypadkach, w których szybkie sortowanie prawdopodobnie będzie działać słabo (głównie posortowane zestawy danych), preferowane jest sortowanie stosu.


4
Szybkie sortowanie działa słabo na przeważnie posortowanym zestawie danych tylko wtedy, gdy wybrano złą metodę wyboru obrotu. Mianowicie, złą metodą wyboru obrotu byłoby zawsze wybieranie pierwszego lub ostatniego elementu jako obrotu. Jeśli za każdym razem wybierany jest losowy obrót i stosowana jest dobra metoda obsługi powtarzających się elementów, szansa na szybkie sortowanie w najgorszym przypadku jest bardzo mała.
Justin Peel

1
@Justin - To prawda, mówiłem o naiwnej implementacji.
zellio

1
@Justin: To prawda, ale szansa na poważne spowolnienie jest zawsze, choćby niewielka. W przypadku niektórych aplikacji mogę chcieć zapewnić zachowanie O (n log n), nawet jeśli jest wolniejsze.
David Thornley,

2

Cóż, jeśli przejdziesz na poziom architektury ... używamy struktury danych kolejki w pamięci podręcznej. Więc to, co kiedykolwiek jest w kolejce, zostanie posortowane. Podobnie jak w przypadku szybkiego sortowania, nie mamy problemu z podzieleniem tablicy na dowolną długość ... ale w stosie sortowanie (przy użyciu tablicy) może się tak zdarzyć, że rodzica może nie być w pod macierzy dostępnej w pamięci podręcznej i wtedy musi umieścić ją w pamięci podręcznej ... co jest czasochłonne. To jest najlepsze szybkie sortowanie !! 😀


1

Heapsort tworzy stertę, a następnie wielokrotnie wyodrębnia maksymalny przedmiot. Jego najgorszym przypadkiem jest O (n log n).

Ale jeśli zobaczysz najgorszy przypadek szybkiego sortowania , którym jest O (n2), zdasz sobie sprawę, że szybkie sortowanie byłoby niezbyt dobrym wyborem w przypadku dużych danych.

To sprawia, że ​​sortowanie jest interesującą rzeczą; Uważam, że przyczyną tak wielu algorytmów sortowania jest dziś to, że wszystkie z nich są „najlepsze” w swoich najlepszych miejscach. Na przykład sortowanie bąbelkowe może wykonać szybkie sortowanie, jeśli dane są posortowane. Lub jeśli wiemy coś o przedmiotach do sortowania, prawdopodobnie możemy zrobić to lepiej.

To może nie odpowiadać bezpośrednio na twoje pytanie, pomyślałem, że dodam moje dwa centy.


1
Nigdy nie używaj sortowania bąbelkowego. Jeśli rozsądnie sądzisz, że Twoje dane zostaną posortowane, możesz skorzystać z sortowania przez wstawianie lub nawet przetestować dane, aby sprawdzić, czy są posortowane. Nie używaj Bubblesort.
vy32

jeśli masz bardzo duży zestaw danych LOSOWO, najlepszym rozwiązaniem jest szybkie sortowanie. Jeśli są częściowo uporządkowane, to nie, ale jeśli zaczniesz pracować z ogromnymi zbiorami danych, powinieneś wiedzieć o nich przynajmniej tyle.
Kobor42

1

Sortowanie na stosie to bezpieczny zakład w przypadku bardzo dużych nakładów. Analiza asymptotyczna ujawnia kolejność wzrostu Heapsort w najgorszym przypadku Big-O(n logn), która jest lepsza niż Quicksort w Big-O(n^2)najgorszym przypadku. Jednak Heapsort jest w praktyce nieco wolniejszy na większości maszyn niż dobrze zaimplementowany szybki sort. Heapsort również nie jest stabilnym algorytmem sortowania.

Przyczyną, dla której sortowanie stosu jest w praktyce wolniejsze niż sortowanie szybkie, jest lepsza lokalizacja odniesienia („ https://en.wikipedia.org/wiki/Locality_of_reference ”) w quicksort, gdzie elementy danych znajdują się w stosunkowo niewielkiej odległości. Systemy, które wykazują silną lokalność odniesienia, są doskonałymi kandydatami do optymalizacji wydajności. Sortowanie na stosie radzi sobie jednak z większymi skokami. To sprawia, że ​​quicksort jest bardziej korzystny dla mniejszych nakładów.


2
Szybkie sortowanie również nie jest stabilne.
Antymon

1

Dla mnie istnieje bardzo podstawowa różnica między sortowaniem heapsort i quicksort: ten ostatni używa rekursji. W algorytmach rekurencyjnych sterta rośnie wraz z liczbą rekurencji. Nie ma to znaczenia, jeśli n jest małe, ale teraz sortuję dwie macierze z n = 10 ^ 9 !!. Program zajmuje prawie 10 GB pamięci RAM, a każda dodatkowa pamięć sprawi, że mój komputer zacznie przełączać się na pamięć dysku wirtualnego. Mój dysk jest dyskiem RAM, ale zamiana na niego powoduje ogromną różnicę w szybkości . Tak więc w pakiecie statystyk zakodowanym w C ++, który zawiera regulowane macierze wymiarów, z rozmiarem nieznanym z góry programiście i nieparametrycznym statystycznym sortowaniem, wolę sortowanie stosu, aby uniknąć opóźnień w przypadku użycia z bardzo dużymi macierzami danych.


2
Potrzebujesz średnio tylko pamięci O (logn). Narzut rekursji jest trywialny, zakładając, że nie masz pecha z obrotami, w którym to przypadku masz większe problemy, o które musisz się martwić.
Antymon

0

w prostych słowach >> HeapSort gwarantował ~ w najgorszym ~ ~ przypadku czas działania „O (n log n)” w przeciwieństwie do ~ średniego ~ czasu działania programu QuickSort wynoszącego „O (n log n)”. QuickSort jest zwykle używany w praktyce, ponieważ zazwyczaj jest szybszy, ale HeapSort jest używany do sortowania zewnętrznego, gdy trzeba posortować duże pliki, które nie mieszczą się w pamięci komputera.


-1

Aby odpowiedzieć na pierwotne pytanie i odnieść się do niektórych innych komentarzy:

Właśnie porównałem implementacje selekcji, szybkiego, scalania i sortowania na stosie, aby zobaczyć, jak zestawią się ze sobą. Odpowiedź brzmi: wszystkie mają swoje wady.

TL; DR: Szybkie to najlepsze sortowanie ogólnego przeznaczenia (dość szybkie, stabilne i głównie na miejscu) Osobiście wolę sortowanie na stosie, chyba że potrzebuję stabilnego sortowania.

Wybór - N ^ 2 - Tak naprawdę jest dobry tylko dla mniej niż 20 elementów, a potem jest lepszy. Chyba że Twoje dane są już posortowane lub bardzo, bardzo blisko. N ^ 2 działa bardzo wolno, bardzo szybko.

Z mojego doświadczenia wynika, że szybko nie zawsze jest tak szybko. Bonusy za używanie szybkiego sortowania jako ogólnego sortowania są jednak dość szybkie i stabilne. Jest to również algorytm lokalny, ale ponieważ jest generalnie implementowany rekurencyjnie, zajmie dodatkową przestrzeń na stosie. Znajduje się również gdzieś pomiędzy O (n log n) a O (n ^ 2). Niektóre rodzaje synchronizacji wydają się to potwierdzać, zwłaszcza gdy wartości mieszczą się w wąskim zakresie. Jest to znacznie szybsze niż sortowanie przez wybór w przypadku 10000000 elementów, ale wolniejsze niż scalanie lub sterty.

Sortowanie przez scalanie jest gwarantowane O (n log n), ponieważ jego sortowanie nie jest zależne od danych. Po prostu robi to, co robi, niezależnie od wartości, które mu nadałeś. Jest również stabilny, ale bardzo duże odmiany mogą wysadzić twój stack, jeśli nie będziesz uważać na implementację. Istnieje kilka złożonych implementacji sortowania przez scalanie w miejscu, ale generalnie potrzebujesz innej tablicy na każdym poziomie, aby scalić wartości. Jeśli te tablice znajdują się na stosie, możesz napotkać problemy.

Sortowanie na stosie to max O (n log n), ale w wielu przypadkach jest szybsze, w zależności od tego, jak daleko musisz przesunąć swoje wartości w górę log n deep heap. Stertę można łatwo zaimplementować na miejscu w oryginalnej tablicy, więc nie wymaga dodatkowej pamięci i jest iteracyjna, więc nie ma obaw o przepełnienie stosu podczas rekurencji. Ogromnym minusem sterty sortowania jest to, że nie jest stabilny porządek, co oznacza, że ma rację, jeśli trzeba, że.


Sortowanie szybkie nie jest sortowaniem stabilnym. Poza tym pytania tego rodzaju zachęcają do odpowiedzi opartych na opiniach i mogą prowadzić do edycji wojen i kłótni. Pytania wymagające odpowiedzi opartych na opiniach są wyraźnie odradzane w wytycznych dotyczących zastrzeżeń. Odpowiadający powinni unikać pokusy udzielenia im odpowiedzi, nawet jeśli mają znaczące doświadczenie i mądrość. Albo oflaguj ich do zamknięcia, albo poczekaj, aż ktoś o wystarczającej reputacji zgłosi je i zamknie. Ten komentarz nie stanowi refleksji na temat Twojej wiedzy ani ważności Twojej odpowiedzi.
MikeC
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.