Kiedy jeden jest bardziej wydajny od drugiego oraz czy:
Quicksort jest stabilny, naturalny?
Mergesort jest stabilny, naturalny?
Teoretycznie obydwa są tak samo wydajne: nie posortują szybciej niż n*logn (generalnie, w modelu obliczeniowym, gdy zamieniamy elementy w miejscu nie można tego dokonać szybciej).
Quicksort ma najgorszy przypadek O(n2) - gdy sortujemy takie same elementy lub posortowana listę; a za to mergesort ma O(nlogn). Ale, quicksort, poprzez odpowiedni wybór piwota (zrandomizowany), praktycznie przywracamy do najgorszego przypadku nlogn.
A teraz czemu quicksort wygrywa? Gdyż jeśli tylko szybkość czytania jest równa(tzn. mamy stały czas dostepu do danych, np. RAM) to jest lepszy, gdyż wykonuje mniej operacji porównań i czytań, oraz wymaga mniej dodatkowej pamięci niż mergesort.
Natomiast gdy mamy duże dane i czytamy je bezpośrednio z dysku - gdzie czytanie sekwencyjne jest szybsze - mergesort, który sobie czyta z tablic - wygrywa.
Dzieki, a jak wyglada sprawa stabilnosci i naturalnosci tych sortowan?
Quicksort jest niestabilny, zaś mergesort stabilny (stabilny - czyli elementy z tymi samymi kluczami są, po posortowaniu w takiej samej kolejności).
O co chodzi z naturalnością?
Naturalność, że dla prawie posortowanej tablicy działa szybciej niż dla całkowicie nie posortowanej.
To tu też quicksort. A tu stronka z porównaniami z animacjami:
https://www.toptal.com/developers/sorting-algorithms/
Czarny Wąż napisał(a):
Kiedy jeden jest bardziej wydajny od drugiego oraz czy:
Quicksort jest stabilny, naturalny?
Mergesort jest stabilny, naturalny?
Mergesort jest znacznie szybszy w praktyce.
@wil jest dokładnie odwrotnie :) Asymptotycznie / teoretycznie mergesort jest "lepszy" bo zawsze daje O(nlog2n)
podczas gdy qsort może dać O(n^2)
, ale w praktyce qsort dla losowych danych jest znacznie szybszy.
Shalom napisał(a):
@wil jest dokładnie odwrotnie :) Asymptotycznie / teoretycznie mergesort jest "lepszy" bo zawsze daje
O(nlog2n)
podczas gdy qsort może daćO(n^2)
, ale w praktyce qsort dla losowych danych jest znacznie szybszy.
Jest wprost przeciwnie: w praktyce qsort jest do niczego - około z 10 razy dłużej trwa sortowanie.
Jest wprost przeciwnie: w praktyce qsort jest do niczego - około z 10 razy dłużej trwa sortowanie.
Jakiś artykuł na potwierdzenie tej tezy? Bo szybki rzut okiem na źródła pokazuje że większość publikacji sugeruje zgoła odmienne wnioski i empirycznie qsort jest szybszy według badaczy. A jeśli to jest introsort to nawet w pesymistycznym przypadku wypada dobrze.
Zresztą sugerujesz że twórcy wszystkich bibliotek standardowych się mylą? Bo właśnie qsort jest tam domyślnym algorytmem sortowania...
qsort z C bierze jako parametr funkcję porównującą. Jeśli kompilator tego nie zoptymalizuje to procesor będzie musiał w kółko wywoływać funkcję. To spowolni sortowanie.
std::sort jest za to szablonem i funkcja porównująca będzie wklejona w instancję szablonu, więc nie powinno być problemów z narzutem na wywołanie funkcji niezależnie od kompilatora.
Shalom napisał(a):
Jest wprost przeciwnie: w praktyce qsort jest do niczego - około z 10 razy dłużej trwa sortowanie.
Jakiś artykuł na potwierdzenie tej tezy? Bo szybki rzut okiem na źródła pokazuje że większość publikacji sugeruje zgoła odmienne wnioski i empirycznie qsort jest szybszy według badaczy. A jeśli to jest introsort to nawet w pesymistycznym przypadku wypada dobrze.
Teoretycy mogą gadać, a nie badać. :)
Zresztą sugerujesz że twórcy wszystkich bibliotek standardowych się mylą? Bo właśnie qsort jest tam domyślnym algorytmem sortowania...
Głupi nigdy się nie myli, bo on nic nie wie.
Nadal obstawiam, że dobrze zrobiony algorytm scalania serii będzie szybszy od qsort.
Jest to zresztą dość oczywiste:
wystarczy zauważyć że 'scalanie' nie jest algorytmem typu 'in situ', a takie są zawsze szybsze -
a przynajmniej mogą być szybsze!
Bowiem takie algorytmy wykorzystują więcej informacji, którą gromadzą w trakcie działania,
i która pozwala potem szybciej zrealizować zadany cel.
PS. odnośnie tego:
raz na jakiś czas pojawia się ewidentny troll, a @Shalom o dziwo wykazuje się anielską cierpliwością
Shalom, jako mój były uczeń, jest już automatycznie dostatecznie rozumny, zatem nie ma potrzeby używać 'specjalnej 'cierpliwości'. :)
Biblioteka standardowa C++ zawiera kilka algorytmów sortowania:
- std::sort, które jest zwykle chyba introsortem (czyli quicksort + z wycofaniem do heapsorta przy degradacji złożoności)
- std:stable_sort, które jest zwykle chyba mergesortem
- std::qsort, które jest (jak się domyślam) quick-sortem bez zabezpieczeń
Przykładowy benchmark jest tutaj: https://stackoverflow.com/a/34668459
std::stable_sort jest zauważalnie wolniejszy od std::sort