Quicksort - pomiar czasu
Procedury związane z losowym quicksortem losowym:
Zadanie 1: Randomized Quicksort (3 pkt)
Napisz i przetestuj program sortujący liczby całkowite metodą Randomized-Quicksort. Wykorzystaj powyższe procedury.
Następnie odpowiedz na pytanie: czy w jeśli tablica jest posortowana przed sortowaniem to Randomized-Quicksort będzie działał szybciej czy wolniej od zwykłego Quicksorta? Dlaczego się tak dzieje? Możesz zaprezentować pomiar czasu obu procedur.
Zadanie 2: Czas różnych przypadków (2 pkt)
Porównaj czas działania poniższych programów sortujących dla tablic wielkości 212,...,218, a wyniki nanieś na wykres.
- Heapsort
- Quicksort
- Randomized-Quicksort