Quicksort vs heapsort

Zarówno quicksort, jak i heapsort wykonują sortowanie na miejscu. Co jest lepsze? Jakie są zastosowania i przypadki, w których jest to preferowane?

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.

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);
}

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.

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

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.

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.

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 !! 😀

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.

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.

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.

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.

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.