Porównanie algorytmów, Mergesort oraz Quicksort.

0

Kiedy jeden jest bardziej wydajny od drugiego oraz czy:
Quicksort jest stabilny, naturalny?
Mergesort jest stabilny, naturalny?

0

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.

0

Dzieki, a jak wyglada sprawa stabilnosci i naturalnosci tych sortowan?

0

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ą?

0

Naturalność, że dla prawie posortowanej tablicy działa szybciej niż dla całkowicie nie posortowanej.

1

To tu też quicksort. A tu stronka z porównaniami z animacjami:
https://www.toptal.com/developers/sorting-algorithms/

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

2

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

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

2

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

0

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.

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

0

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

1

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1