Zadanie 1. Sortowanie

Termin przysłania sprawozdania: 7.04.2025 (tylko PDF!)

Przebieg ćwiczenia:

I.
Porównaj szybkość działania 3 metod sortowania prostego: Bubble Sort, Insertion Sort, Selection Sort dla tablicy liczb całkowitych generowanych losowo.
Wyniki pomiarów przedstaw na wykresie t = f(n), gdzie: t - czas sortowania; n - liczba elementów tablicy.
Liczbę elementów należy dobrać w taki sposób, aby możliwe było wykonanie pomiarów. Wyniki przedstaw na 1 wykresie dla 15 punktów pomiarowych.

II.
Porównaj szybkość działania 3 metod sortowania szybkiego: Heap Sort, Merge Sort, Quick Sort dla tablicy liczb całkowitych generowanych losowo.
Wyniki pomiarów przedstaw na wykresie t = f(n), gdzie: t - czas sortowania; n - liczba elementów tablicy.
Liczbę elementów należy dobrać w taki sposób, aby możliwe było wykonanie pomiarów. Wyniki przedstaw na 1 wykresie dla 15 punktów pomiarowych.

Dla wykresów z punktów I i II sformułuj wnioski odnośnie złożoności obliczeniowej badanych metod i ich związku z efektywnością sortowania oraz zajętością pamięciową każdej z nich.

III.
Porównaj efektywność działania czterech algorytmów sortowania Insertion Sort, Selection Sort, Heap Sort, Merge Sort
dla danych wejściowych w postaci tablic:
losowej, posortowanej rosnąco, posortowanej malejąco, stałej i v-kształtnej.
Przedstaw 4 wykresy t = f(n) każdej metody sortowania osobno dla 5-ciu typów danych wejściowych.
Liczbę elementów należy dobrać w taki sposób, aby możliwe było wykonanie pomiarów.

Sformułuj wnioski odnośnie wpływu postaci ciągów wejściowych na czas sortowania (najgorsze, nalepsze przypadki).

IV.
Zaimplementuj algorytm Quicksort w wersji rekurencyjnej z różnymi sposobami wyboru klucza:
skrajnie prawego, środkowego co do położenia, losowego.
Utwórz wykres porównujący efektywność działania algorytmu w zależności od wyboru klucza dla A-kszytałtnego ciągu wejściowego.

Sformułować wnioski dotyczące wpływu wyboru klucza na działanie algorytmu (najgorsze, najlepsze przypadki)?

Pseudokody
Pseudokod Quicksort - wersja iteracyjna