Algorytmy sortowania
- sortowanie przez proste wybieranie (selection sort)
- sortowanie przez proste wstawianie (insertion sort)
- sortowanie przez prostą zamianę (bubble sort)
- sortowanie przez kopcowanie (heapsort)
- sortowanie przez zliczanie (counting sort)
- sortowanie przez scalanie (merge sort)
- sortowanie za pomocą malejących przyrostów (shell sort)
- sortowanie szybkie (quicksort)
Termin oddawania programów i wyników eksperymentów (+ wykresy): 21.03.2017
Termin dostarczenia sprawozdania (mailem pdf): 28.03.2017
Zadania
- zaimplementuj następujące algorytmy: insertion sort, bubble sort, selection sort oraz merge sort
- wygeneruj n-elementowe zbiory wejściowe; ciąg danych jest ułożony w sposób losowy, rosnący, malejący, stały, A-kształtny (rosnąco-malejący, np. 1,3,5,7,9,8,6,4,2)
Dla 10 różnych wartości n (dobrane wartości tak, żeby można było dokonać pomiaru czasu) utwórz następujące wykresy t=f(n)
- porównaj dla każdego algorytmu efektywność jego działania w zależności od danych wejściowych (4 wykresy – dla każdego algorytmu)
- porównaj dla każdego rodzaju danych wejściowych efektywność działania różnych algorytmów (5 wykresów – dla każdego rodzaju danych wejściowych)
Zaimplementuj algorytm quicksort w dwóch różnych implementacjach: rekurencyjnie oraz iteracyjnie (z własną implementacją stosu). Dla obu wersji porównaj różne sposoby wyboru klucza do porównania: skrajnie prawego, losowo wybranego elementu ciągu. Utwórz 2 wykresy porównujące efektywność działania algorytmów w zależności od wyboru różnego klucza.
- porównaj na każdym wykresie efektywność działania algorytmu w zależności od danych wejściowych (ciąg liczb: malejący, stały, losowy, A-kształtny) dla 10 różnych wartości n
Do sprawozdania: Jaka jest złożoność badanych algortymów? Czy rozkład danych wejściowych wpływa na działanie algorytmu (najgorsze, najlepsze przypadki)?
Materiały: