Sprawozdania Algorytmy i Struktury Danych, PUT Informatyka, semestr II
Politechnika Poznańska Informatyka, semestr II Algorytmy i Struktury Danych Michał Zieliński INF5.1 148064
Cel sprawozdania:
zaimplementowanie podstawowych algorytmów sortowania w języku Python
porównanie czasu wykonania algorytmów dla różnych typów danych wejściowych
przetestowanie algorytmów
porównanie złożoności czasowej algorytmów
Algorytmy:
1.Selection Sort
2.Insertion Sort
3.Bubble Sort
4.Quick Sort
5.Merge Sort
6.Heap Sort
7/Counting Sort
Algorytmy sprawdzam dla danych:
1.losowych (3 razy)
2.wartości stałej
3.posortowanych rosnąco
4.posortowanych malejąco
5.w kształcie A
6.w kształcie V
Algorytm przegląda tablicę n razy i za każdym razem umieszcza najmniejszy element na początku. Sortowanie w miejscu. Algorytm niestabilny. Złożoność czasowa O(n^2), gdyż w każdym przypadku wykonują się dwie zagnieżdżone pętle.
Dla wszystkich typów danych otrzymujemy podobny czas sortowania. W każdym przypadku algorytm przechodzi przez dwie pętle.
intuicyjny w implementacji algorytm, niestety bardzo wolny
Algorytm wstawia kolejne elementy zbioru nieposortowanego na odpowiednie miejsce w zbiorze posortowanym. Sortowanie w miejscu. Algorytm stabilny.Złożoność czasowa O(n^2), gdyż w każdym przypadku wykonują się dwie zagnieżdżone pętle.
Znowu otrzymaliśmy podobne wyniki dla wszystkich typów danych wejściowych.
intuicyjny w implementacji algorytm, niestety bardzo wolny
Algorytm przechodzi po kolejnych indeksach tablicy. Porównuje dwa sąsiednie elementy i zamienia jeśli są w złej kolejności. Sortowanie w miejscu. Algorytm stabilny. Średnia i pesymistyczna złożoność czasowa to O(n^2), a optymistyczna O(n), gdy dane są posortowane.
Otrzymujemy podobne wyniki dla wszystkich typów testów. Najgorszy wynik otrzymujemy dla danych posortowanych malejąco, gdyż bąbelek zawsze przechodzi do końca tabeli. Dla danych posortowanych złożoność czasowa jest najlepsza.
ten algorytm jest już bardziej optymalny dla pewnych typów danych niż dwaj poprzednicy
Podejście dziel i zwyciężaj. Algorytm wybiera pivot jako losowy element z tablicy i dzieli ją na dwie podtablice. W pierwszej umieszczamy elementy większe od pivota, a w drugiej mniejsze. Wywołujemy algorytm rekurencyjnie na podtablicach aż do momentu, gdy długość tablicy będzie mniejsza bądź równa 1. Najgorsza złożoność występuje, gdy zawsze wybieramy skrajną (maksymalną, bądź minimalną) wartość jako pivot. Wynosi O(n^2). Optymistyczna złożoność czasowa O(n) występuje, gdy zawsze wybieramy medianę jako pivot. A średnia złożoność czasowa wynosi O(n*logn)
Podobny czas dla wszystkich testów, gdyż w algorytmie wybieramy losowo pivota, a testy tego nie uwzględniają. Zdecydowanie najlepiej wypadają wartości stałe gdyż nie wchodzą one do wywołań rekurencyjnych.
algorytm wyraźnie szybszy od naiwnych, jednak jego implementacja jest odrobinę bardziej skomplikowana; napotkałem na problemy z implementacją tego algorytmu, by działał w miejscu. Dla danych do 1mln nie zauważyłem przez to spadków wydajności. Tworząc podtablice z wartościami mniejszymi, większymi i równymi pivotowi, algorytm bardzo dobrze radzi sobie z danymi o stałych wartościach.
Podejście dziel i zwyciężaj. Algorytm dzieli tablicę na pół rekurencyjnie, aż do uzyskania podtablic o długości jeden, które są posortowane. Następnie od ostatniego wywołania funkcji łączymy dwie posortowane podtablice w jedną która jest wynikiem tego wywołania. Algorytm stabilny. Złożoność czasowa O(n*logn) dla każdego przypadku.
Dla wszystkich wartości złożoność czasowa jest bardzo podobna.
otrzymałem gorsze wyniki dla tego algorytmu niż w przypadku quicksorta, jednak algorytm był łatwiejszy w implementacji.
Algorytm bazuje na strukturze kopca. Elementy rodzice (indeks k) mają dzieci o indeksach 2k+1 i 2k+2 Najpierw funkcja heapify() rozpatruje rodzica i dzieci i zamienia ich miejscami w ten sposób, że w korzeniu poddrzewa znajduje się element o największej wartości. Funkcja ta jest wykonywana na wszystkich rodzicach od ostatniego. Kopiec się rozrasta i elementy ustawiają się na odpowiednich miejscach. Sortowanie w miejscu. Złożoność czasowa O(n*logn)
Algorytm wykazuje podobną złożoność czasową, dla każdego typu danych. Najlepszy wynik otrzymujemy dla danych stałych.
zdecydowanie najtrudniejszy algorytm w implementacji z tutaj przedstawionych, napotkałem trudności w tworzeniu funkcji, która ustawia rodzica z dziećmi w dobrej hierarchii oraz w odpowiednim wywołaniu tej funkcji; działa jednak bardzo szybko
Algorytm stosuje dodatkową tablicę pomocniczą, która zlicza ilość wystąpień każdego elementu. Następnie elementy są zwracane. Złożoność czasowa O(n +k). Przypadek pesymistyczny następuje, gdy dane mają duży zakres, a część liczb z zakresu nie znajduje się w tablicy np. [5, 500000].
Algorytm można stosować tylko na liczbach całkowitych. Jest za to bardzo szybki, jeśli liczby nie mają o wiele większego zakresu od długości tablicy. Algorytm nie wykonuje porównań.
najbardziej przyjemny w implementacji ze wszystkich przedstawionych algorytmów, bardzo szybko działa oraz nie sprawia problemów w implementacji; jednak ma duże ograniczenia ze względu na typ sortowanych danych oraz ich zakres
Do sprawdzenia działania algorytmów zastosowałem testy jednostkowe.
Trzy pierwsze testy wygenerowałem za pomocą liczb pseudolosowych. Są to tablice o losowej długości z zakresu 1 - 10000 z liczbami z zakresu 0-1000.
Test czwarty jest to sprawdzenie algorytmu dla stałej wartości dla wszystkich elementów.
Test piąty i szósty są to liczby posortowane rosnąco i malejąco.
Ostatni test jest to “piramida”, gdzie pierwsza połowa tablicy jest posortowana rosnąco, a druga malejąco.
Poniżej umieszczam tylko implementację testu dla piramidy.
Reszta testów jest dostępna w repozytorium github.
import unittest
import sorts
from random import randint
class MyTestCase(unittest.TestCase):
def testPyramid(self):
tabLenght = randint(1, 10000)
tab = [0] * tabLenght
for i in range(tabLenght):
tab[i] = randint(0, 200)
half1 = sorted(tab[0:len(tab)//2])
half2 = sorted(tab[(len(tab)//2) + 1 ::], reverse=True)
tab = half1 + half2
tabSort = sorted(tab)
self.assertEqual(sorts.selectionSort(tab), tabSort)
self.assertEqual(sorts.insertionSort(tab), tabSort)
self.assertEqual(sorts.bubbleSort(tab), tabSort)
self.assertEqual(sorts.quickSort(tab), tabSort)
self.assertEqual(sorts.mergeSort(tab), tabSort)
self.assertEqual(sorts.heapSort(tab), tabSort)
self.assertEqual(sorts.countingSort(tab), tabSort)
if __name__ == '__main__':
unittest.main()Tworzę po 100 testów dla każdej wielkości danych [50, 100, 200, 300, 500, 1000] Test zapełniam liczbami pseudolosowymi z zakresu 0-1000. Wywołuję funkcje sortowania dla każdego pliku wejściowego i zapisuję wynik oraz czas plikach wyjściowych. Czas mierzę za pomocą biblioteki timeit.
Stworzyłem wykres za pomocą biblioteki matplotlib. I zestawiłem na nim średni czas sortowania danych przez dany algorytm w zależności od wielkości danych wejściowych.
W moim przypadku najgorszą efektywnością wykazał się algorytm Bubble Sort Niewiele gorzej również wypadły Insert Sort oraz Select Sort. Są to wszystkie algorytmy o średniej złożoności obliczeniowej O(n^2) Znacznie lepsze rezultaty można zauważyć w algorytmach Quick Sort i Merge Sort, algorytmach reprezentujących podejście dziel i zwyciężaj. Najlepiej wypadły algorytmy Heap Sort i Counting Sort.
Data dostępu: 12.03.2021r https://ekursy.put.poznan.pl/pluginfile.php/1046084/mod_resource/content/4/Frohmberg-ASD-temat-1.pdf https://pl.wikipedia.org/wiki/Sortowanie_przez_kopcowanie https://www.geeksforgeeks.org/heap-sort/ https://www.youtube.com/watch?v=M2bKENbdnI4 https://www.geeksforgeeks.org/merge-sort/ https://www.geeksforgeeks.org/quick-sort/ https://www.geeksforgeeks.org/insertion-sort/ https://pl.wikipedia.org/wiki/Sortowanie_przez_wybieranie https://www.geeksforgeeks.org/bubble-sort/ https://stackoverflow.com/questions/18262306/quicksort-with-python https://matplotlib.org/stable/users/index.html