POLITECHNIKA WROCŁAWSKA wydział Elektroniki kierunek Automatyka i Robotyka Projektowanie algorytmów i metody sztucznej inteligencji Wersja 2 poprawiona
Data wykonania
12.04.2012
Grupa
Piątek, godzina 10:15
Autor

Wprowadzenie

Celem ćwiczenia jest zbadanie złożoności obliczeniowej i pamięciowej czterech algorytmów sortowania: bąbelkowego, QuickSort, przez kopcowanie oraz pozycyjnego, a także zbadanie struktur takich jak lista, kolejka, czy stos.

Badania algorytmów sortowania zostały wykonane dla różnego typu danych wejściowych (posortowanych lub losowych) oraz dla różnych struktur przechowujących dane (tablica, lista). Wyniki badań dla poszczególnych algorytmów zostały przedstawione w dalszej części sprawozdania.

Pomiar czasu został zrealizowany przy pomocy biblioteki time.h. Przed startem samego algorytmu zapisano aktualny czas systemowy w jako zmienną typu clock_t za pomocą funkcji clock(). Podobny czas zanotowano na końcu działania algorytmu. Zmierzony czas jest to różnica pomiędzy czasem początkowym a końcowym. Podany wynik jest wyrażony w milisekundach. Wspomniana metoda nie należy do zbyt dokładnych, więc podane wartości czasu są wartościami średnimi obliczonymi na podstawie kilku prób. Programy były kompilowane w opcji Debug.

Badania zostały wykonane na laptopie DELL INSPIRON N5110 z procesorem Intel Core i5-2430M 2.40GHz. Wyniki mogły zostać zafałszowane przez system, który często bez wiedzy użytkownika wykonuje inne działania w tle. Do wykonania sprawozdania wykorzystano napisane wcześniej programy. Jednak znaczna większość z nich musiała zostać zmodyfikowana w celu pomiaru czasu działania. W tabeli nr 1 znajdują się szacunkowe daty powstania pierwotnych, niezmodyfikowanych wersji algorytmów.

Tabela 1. Daty utworzenia poszczególnych algorytmów.
Lp.
1.
2.
3.
4.
5.
6.
7.

Lista, kolejka, stos

Lista jest strukturą, która pozwala na dostęp do wszystkich elementów (jako jedyna struktura z opisywanych). Można do niej dodawać oraz usuwać elementy zarówno na początku jak i na końcu. Stos jest nieco okrojoną wersją listy, pozwala jedynie na dostęp do początku. Kolejka natomiast, pozwala dodawać elementy na jeden koniec, a usuwać tylko z drugiego. Lista może być dwukierunkowa, co powoduje zwiększenie złożoności pamięciowej (dodatkowy wskaźnik w każdym elemencie), jednak zmniejsza złożoność czasową niektórych operacji. Z powodu tego podobieństwa przeanalizowana została jedynie lista. Wszystkie trzy formy zostały zrealizowane w podobny sposób. Każdym elementem listy/kolejki/stosu jest obiekt przedstawiony poniżej.

struct elem

{

int wartosc;

elem * nast;

};

Pomiary wykonano dla 200 000 elementów, mierząc czas operacji dla każdych kolejnych 20 000. Pomiary czasu dodawania elementów na początek, usuwania z początku oraz usuwania z końca dały podobny wynik, taki sam, niezależnie od ilości elementów, wynoszący 5-6ms na każde 20 000 elementów. Jedynie dla dodawania na koniec listy czas ten był znacząco inny i został przedstawiony w tabeli nr 2.

Tabela 2. Czas dodawania kolejnych partii 20-elementowych w zależności od już zapisanej liczby danych.
Liczba elementów po operacji (x 1 000)
Czas operacji [ms]

Wykres 1. Czas dodawania elementów na koniec listy.

Sortowanie bąbelkowe

Sortowanie bąbelkowe składa się z dwóch pętli for, jedna wewnątrz drugiej. Algorytm w pętli porównuje dwa kolejne elementy i, jeśli pierwszy jest większy od drugiego, zamienia je miejscami. Aby posortować tablicę n-elementową, należy taką pętlę wykonać n razy. Złożoność obliczeniowa wynosi zatem O(n²). Poniżej przedstawiono fragment kodu odpowiedzialny za sortowanie.

for(int i=0; i<d; i++)

for(int j=0; j<d-1; j++)

if(tablica[j]>tablica[j+1])

{

int elem=tablica[j];

tablica[j]=tablica[j+1];

tablica[j+1]=elem;

}

Złożoność pamięciowa dla podanej metody sortowania wynosi tyle ile, rozmiar tablicy zawierającej elementy do posortowania, czyli n*int plus jedna zmienna pomocnicza. Zmienna typu int zajmuje 4 bajty pamięci, zatem złożoność pamięciowa całego algorytmu wynosi 4n bajtów plus jeden int służący do zamiany miejscami elementów. Zatem złożoność całkowita wynosi O(n), zaś pomocnicza O(1).

Tabela 3. Czas sortowania bąbelkowego tablicy wyrażony w sekundach.
l. elementów
dane losowe [ms]
dane rosnące [ms]
dane malejące [ms]

Tabela 4. Czas sortowania bąbelkowego listy wyrażony w sekundach.
l. elementów
dane losowe [ms]
dane rosnące [ms]
dane malejące [ms]

Wykres 2. Sortowanie bąbelkowe tablicy.

Wykres 3. Sortowanie bąbelkowe listy.

Wnioski

1. Sortowanie tablicy jest znacznie szybsze niż sortowanie listy. Widać to w tabelach nr 3 i 4. Np. czas sortowania 40 000 elementów w tablicy zajęło niewiele ponad 7s, zaś posortowanie 150 elementów umieszczonych na liście zajęło ponad 8,5s. Spowodowane jest to faktem, że aby dostać się do dowolnego elementu listy należy ją przeszukać, co zajmuje dużo czasu.

2. Różnica między sortowaniami dla dwukrotnie lub trzykrotnie większej liczby elementów powoduje odpowiednio cztero- lub dziewięciokrotny przyrost czasu trwania algorytmu. Potwierdza to złożoność obliczeniową wynoszącą O(n²).

3. Dla tablicy najszybciej przebiegało sortowanie danych poukładanych rosnąco, najwolniej natomiast sortowanie danych losowych. Dla listy natomiast, najwolniej posortowały się dane ułożone malejąco.

4. Czas sortowań wskazuje na poprawne zaimplementowanie i realizację idei sortowania bąbelkowego.

Sortowanie przez kopcowanie

Sortowanie przez kopcowanie polega na utworzeniu kopca typu max, tzn. tablicy rozpatrywanej jako prawie pełne drzewo binarne, w którym rodzic jest zawsze równy lub starszy od swych dzieci. W tym momencie w korzeniu znajduje się największy z elementów. Po odłożeniu go na koniec tablicy, wstawiamy w jego miejsce ostatni z liści po czym przywracamy własność kopca, zamieniając wstawiony element ze starszym dzieckiem tak długo, aż drzewo znów będzie kopcem. Wykonując te czynności powoli odkładamy kolejne największe elementy z drzewa. Złożoność obliczeniowa takiego algorytmu wynosi O(nlogn).

Złożoność pamięciowa dla podanej metody sortowania wynosi tyle ile, rozmiar tablicy zawierającej elementy do posortowania, czyli n*int plus jedna zmienna pomocnicza. Zmienna typu int zajmuje 4 bajty pamięci, zatem złożoność pamięciowa całego algorytmu wynosi 4n bajtów plus jeden int służący do zamiany miejscami elementów. Zatem złożoność całkowita wynosi O(n), zaś pomocnicza O(1).

Tabela 5. Czas sortowania przez kopcowanie tablicy, wyrażony w sekundach.
l. elementów [x1 000 000]
dane losowe [ms]
dane rosnące [ms]
dane malejące [ms]

Tabela 6. Czas sortowania przez kopcowanie listy, wyrażony w sekundach.
l. elementów
dane losowe [ms]
dane rosnące [ms]
dane malejące [ms]

Wykres 4. Sortowanie przez kopcowanie tablicy.

Wykres 5. Sortowanie przez kopcowanie listy.

Wnioski

1. Ponownie sortowanie tablicy jest znacznie szybsze niż sortowanie listy.

2. Wykresy przedstawiające wyniki badań przypominają wykres funkcji nlogn.

3. Dla tablicy najszybciej przebiegało sortowanie danych poukładanych malejąco, najwolniej natomiast sortowanie danych rosnących. Dla listy natomiast, najwolniej posortowały się dane ułożone malejąco, a najszybciej dane rosnące.

4. Kształt wykresu oraz dane liczbowe pozwalają przypuszczać, że idea sortowania przez kopcowanie została zrealizowana poprawnie. Algorytm oparty na tablicy jest taki sam, jak ten, oparty na liście, różnią się jedynie sposobem dostępu do danego elementu.

Sortowanie szybkie (QuickSort)

Sortowanie szybkie (tzw. QuickSort) jest algorytmem rekurencyjnym. Ze względu na swoją konstrukcję program przerywał działanie algorytmu dla danych posortowanych rosnąco, wyświetlając błąd o przepełnieniu stosu. Dopiero po programowym zwiększeniu stosu, algorytm działał normalnie. Wymusiło to jednak drastyczną zmianę liczby elementów sortowanych. Złożoność czasowa takiego algorytmu wynosi O(nlogn). Na złożoność pamięciową składa się tablica (lub lista) zawierająca liczby do posortowania oraz dwie dodatkowe zmienne typu int. Pierwsza odpowiada za zamianę dwóch elementów między sobą, a druga zaś służy jako wskaźnik, który element stanowi punkt podziału tablicy (listy).

Tabela 7. Czas sortowania szybkiego tablicy.
l. elementów (x 1 000)
dane losowe
l. elementów (x 1 000)
dane rosnące
dane malejące

Tabela 8. Czas sortowania szybkiego listy.
l. elementów
dane losowe
l. elementów
dane rosnące
dane malejące

Wykres 5. Sortowanie szybkie tablicy (dla czytelności usunięto niektóre znaczniki).

Wykres 6. Sortowanie szybkie listy (dla czytelności usunięto niektóre znaczniki).

Wnioski

1. Kolejny raz sortowanie tablicy jest znacznie szybsze niż sortowanie listy.

2. Wykresy przedstawiające wyniki badań przypominają wykres funkcji nlogn.

3. Ze względu na przepełnianie stosu, należało zmienić liczbę sortowanych elementów. Sortowanie już posortowanych danych (rosnąco lub malejąco) zajmowało znacznie więcej czasu, niż sortowanie danych losowych. Wynika to najprawdopodobniej z samej metody. Wzór algorytmu został zaczerpnięty z literatury do przedmiotu. Elementem rozdzielającym jest ostatni element z badanego przedziału. Oznacza to, w przypadku liczb posortowanych, wartość największą lub najmniejszą, a to z kolei przekłada się na dużą ilość wykonanych zamian.

4. W obu przypadkach najszybciej przebiegało sortowanie danych losowych, znacznie wolniej sortowanie danych malejących, natomiast najwolniej sortowanie danych rosnących.

5. Kształt wykresu oraz dane liczbą pozwalają przypuszczać, że idea sortowania szybkiego została zrealizowana poprawnie.

Sortowanie pozycyjne

Sortowanie pozycyjne zostało zrealizowane przy pomocy algorytmu sortowania przez zliczanie, który jest algorytmem stabilnym. Pozwala to uniknąć porównań kolejnych elementów, a co za tym idzie zmniejszyć złożoność obliczeniową poniżej granicy O(nlogn). Ostatecznie złożoność obliczeniowa tego algorytmu jest liniowa, wynosi O(n). Jednak odbywa się to kosztem złożoności pamięciowej, gdyż potrzebne są trzy dodatkowe tablice. Pierwsza przechowuje ilość elementów mniejszych bądź równych i ma rozmiar 10*int. Druga przechowuje cyfry sortowane (odpowiednie pozycje), do trzeciej zaś zapisywany jest wynik sortowania. Dwie ostatnie zajmują tyle samo pamięci, co tablica danych wejściowych.

Tabela 9. Czas sortowania pozycyjnego tablicy.
l. elementów (x 1 000 000)
dane losowe
dane rosnące
dane malejące

Tabela 10. Czas sortowania pozycyjnego listy.
l. elementów
dane losowe
dane rosnące
dane malejące

Wykres 7. Sortowanie pozycyjne tablicy.

Wykres 8. Sortowanie pozycyjne listy.

Wnioski

1. Znów sortowanie tablicy jest znacznie szybsze niż sortowanie listy.

2. Sortowanie listy ma większą złożoność obliczeniową niż sortowanie tablicy, z powodu wyszukiwania elementów na liście.

3. Sortowanie ma zbliżony czas działania, bez względu na rodzaj danych wejściowych.

4. Liniowość czasu sortowania tablicy pozwala przypuszczać, że algorytm został zrealizowany poprawnie.

Drzewo BST

Złożoność czasowa operacji na drzewie jest zależna od jego wysokości. Pesymistyczny wariant to O(n), kiedy wysokość drzewa równa jest liczbie węzłów (każdy węzeł ma tylko jedno dziecko). Jeśli drzewo jest pełne, to jego wysokość wynosi logn, czyli złożoność czasowa wynosi O(logn). Wszystkie pomiary wykonano kilkukrotnie, a przedstawiony czas jest średnią arytmetyczną z otrzymanych.

Tabela 11. Czas operacji dodawania do drzewa BST.
l. elementów (x1 000)
czas dodawania [ms]

Tabela 12. Czas operacji wyszukiwania 100 000 razy losowego elementu w drzewie BST.
l. elementów (x1 000)
czas wyszukiwania [ms]

Tabela 13. Czas operacji usuwania 100 000 elementów z drzewa BST.
l. elementów (x1 000)
czas usuwania [ms]

Wykres 9. Dodawanie elementów do drzewa BST.

Wnioski

1. Czas dodawania elementów do drzewa BST rośnie wraz z liczbą elementów nieliniowo. Wygląd wykresu przypomina wykres funkcji logn, zatem można przypuszczać, że algorytm został zaimplementowany poprawnie.

2. Liniowy czas wyszukiwania i usuwania elementów wynika z zakresu liczb umieszczanych w drzewie. Jeśli zakres jest kilkukrotnie mniejszy od liczby elementów w drzewie, istnieje duże prawdopodobieństwo, że elementy się powtarzają. Oznacza to, że algorytm nie musi przeszukać całego drzewa, tylko jego część, porównywalną niezależnie od wysokości.

3. Nie udało się zmierzyć czasu usuwania 100 000 elementów, gdy drzewo składało się ze 100 000 elementów, gdyż algorytm losował dowolny węzeł i go usuwał. W końcowej fazie ciężko było trafić w istniejące elementy (wartości), gdyż zakres losowania danych był duży i coraz ciężej było znaleźć istniejącą w drzewie liczbę. Po wielokrotnym losowaniu przypadkowych wartości algorytm przerywał swoje działanie z błędem.

Wnioski końcowe

1. Absurdem jest przechowywanie sortowanych danych na liście. Powoduje to znaczące zwiększenie złożoności obliczeniowej.

2. Najszybszym algorytmem sortowania jest sortowanie pozycyjne, odbywa się to jednak kosztem potrzebnej pamięci.

3. Najszybszym algorytmem spośród "oszczędnych" pamięciowo okazało się sortowanie przez kopcowanie.

4. Wszystkie algorytmy, poza QuickSortem mają zbliżone czasy sortowań dla danych losowych, rosnących czy malejących. Jedynie w sortowaniu szybkim widać bardzo znaczącą różnicę pomiędzy sortowaniem danych losowych, a posortowanych.