Heapsort - pomiar czasu
W rozwiązaniu poniższych zadań przydatna będzie umiejętność pomiaru czasu wykonania obliczeń w programie. Można to zrobić odczytując czas systemowy przed obliczeniami i po obliczeniach, a następnie odejmując jedną wartość od drugiej. Tutaj przykładowe programy pokazujące jak to się robi czas1.c (dr P.Pączkowski) i czas2.c (mój) - wybierzcie sposób, który bardziej do was przemamwia i wydaje się bardziej poprawny.
Sprawdź, czy rzeczywisty czas działania algorytmu Heapsort zgadza się z teoretycznym oszacowaniem O(n*lg n).
W tym celu należy uruchom procedurę sortowania na danych o różnej długości n (niech to będzie 100, 1000, 10000, 20000, 30000) mierząc w programie rzeczywisty czas T(n) działania procedury sortującej i wyliczyć ilorazy (n*lg n)/T(n).
Należy wygenerować w programie tabelkę postaci:
| n | T(n) | (n*lg n)/T(n) |
| 100 | ... | ... |
| 1000 | ... | ... |
| ... | ... | ... |
Jeżeli czas rzeczywisty zgadza się z teoretycznym oszacowaniem, otrzymane ilorazy w trzeciej kolumnie powinny wyjść mniej więcej stałe.
Naszym celem będzie pomiar czasu sortowania kopcowego (tak jak w poprzednim zadaniu), ale tym razem porównamy efektywność Heapsort z popularnym algorytmem sortowania bąbelkowego (Bubblesort).
- Zmierz ile czasu będzie działać Heapsort na losowo wygenerowanej tablicy o wielkości 28 elementów (liczby całkowite z zakresu -30000..30000). Dla tej samej tablicy zbadaj czas działania Bubblesort.
- Pomiar wykonaj 10 razy dla różnych danych i podaj uśredniony wynik dla obu procedur sortujących.
- Następnie podobnie wykonaj pomiary dla tablicy wielkości 29, 210, ..., 216 elementów.
- Wyniki zbierz w tabeli, a następnie stwórz wykres liniowy na ich podstawie (oś X: wielkość tablicy, oś Y: czas, legenda: procedura). Wykres zapisz jako obrazek i przedstaw swoje wnioski