Merge Sort vs Heap Sort - czas

Cześć,

Brałem kody sortowań ze strony "geeksforgeeks", troche go przerabiajac. Porównuje sobie wyniki czasu z roznym rozmiarem tablicy. Mam kilka pytań:

1. W MergeSort nie mogę sortować tablicy z rozmiarami powyzej 600 000, wywala mi blad Process returned -1073 ... itd. Czy to normalne? Przy mniejszach tablicach kod działa bez zarzutu. Merge Sort nie radzi sobie z większymi?
2. Porownujac czas dla tych dwóch mam takie wyniki np. dla 500 000, Msort = ok. 170 milisekund, Hsort = ok. 310, gdzie elementy są losowane rand()%100. Czy to są dobre wyniki? Chciałbym się upewnić że te dwa algorytmy mi działają dobrze. Chociaż z tego co czytałem trochę po internecie faktycznie czytałem że HeapSort radzi sobie gorzej od Merge'a, głównie dlatego że Heap Sort jest dosyć niestabilny.

Może poczytaj o charakterystykach tych algorytmów. Dla dużych tablic rand()%100 użyj algorytm kubełkowy.

Dobra, jeszcze poczytam o tym. Tak w ogóle zauważyłem że jak zwiększe rand()%10000 i ustawie tablice na milion to kod działa. MergeSort nie radzi sobie z powtarzającymi się elementami?

Radzi sobie - tylko Ty możesz mieć skopana implementację...

Merge potrzebuje O(n) dodatkowej pamięci.
Więc możliwe że masz za mało pamięci w komputerze lub jakiś przestarzały system, lub jakiś przestarzały kompilator, lub zwyczajnie skopaną implementacje.

AdaKo napisał(a):

Cześć,

Czy to są dobre wyniki?

Najprawdopodobniej: Nie.
Testowanie wydajności kodu jest dość trudną rzeczą. łatwo popełnić błędy, które mają poważne konsekwencje dla wyników końcowych.

Nie widząc:

• testowanego kodu
• kodu testującego
• rodzaju kompilatora i jego ustawień

Najlepsza odpowiedź, to właśnie: "najprawdopodobniej: nie."

t = nlog2(n) =

n = 512 k => 512k * 19 =~ 10 mln oper
co dla 1GHz daje czas: 1/100 s = 10ms.

nie wiem na czym to uruchamiasz.. w główce? :)

Oba algorytmy mają podobną złożoność czasową i pamięciową.
Heapsort nie wymaga O(n) dodatkowej pamięci, Mergesort wymaga O(n) - jeśli go zrobisz in-place na kopii danych.
Rozmiar tablicy nie powinien mieć żadnego znaczenia, chyba że alokujesz obszary w okolicach 4 GB.

vpiotr napisał(a):

Heapsort wymaga O(n) dodatkowej pamięci

A na co mu? Podstawowe heapsorty wymagają O(1) dodatkowej pamięci. O(n) to byłoby jakbyś coś przykombinował.

https://en.wikipedia.org/wiki/Heapsort

Worst-case space complexity: O(n) total, O(1) auxiliary

Co do MergeSorta, który wywala się na dużych tablicach - czy przypadkiem nie alokujesz dodatkowej tablicy na stosie zamiast na stercie?

AdaKo napisał(a):

Chciałbym się upewnić że te dwa algorytmy mi działają dobrze. Chociaż z tego co czytałem trochę po internecie faktycznie czytałem że HeapSort radzi sobie gorzej od Merge'a, głównie dlatego że Heap Sort jest dosyć niestabilny.

Stabilność sortowania dotyczy zachowania kolejności elementów (jeśli sortujemy po kawałku danych, czyli kluczu, a nie po całości), a nie błędów w implementacji. https://pl.wikipedia.org/wiki/Sortowanie#Klasyfikacja

A co to za problem: sortowanie liczb int?
wystarczy to policzyć, przekopiować i cześć: 2n operacji; speed: 4miliardy /s! :)

A co to za problem: sortowanie liczb int?

Poczytaj https://www.hindawi.com/journals/jcnc/2019/3027578/

kwalifika napisał(a):

A co to za problem: sortowanie liczb int?

Żaden problem, ludzie wciąż doktoraty bronią z tego zakresu.