Algorytmy i Struktury Danych
v.1/ 2009
Laboratorium 2
Badanie złożoności obliczeniowej algorytmów na przykładzie algorytmów sortowania
1. Cel ćwiczenia
Celem ćwiczenia jest praktyczne zapoznanie się z pojęciem złożoności obliczeniowej algorytmów na
przykładzie wybranych algorytmów sortowania.
2. Kody z
ródłowe - opis
Wszystkie algorytmy badane w trakcie ćwiczenia zostały zaimplementowane jako metody szablonowej klasy
wirtualnej AlgorytmySortowania (R.1), pochodnej od wykorzystywanej w ćwiczeniach 2 i 3 klasy AISD (R.2).
template
class AlgorytmySortowania:public AISD{
protected:
int Rozdziel(int L=0, int R=0); // quicksort (QS) podzial zbioru
void QuickSortRekur(int L,int R); // QS standardowy
void QuickSortRekurFactorM(int L,int R,int M); // QS + poprawka na male zbiory
void QuickSortRekurMediana(int L,int R,int M); // QS + mediana z 3
void PrzezWstawianie2QS(int L, int R); // sortowanie przez wstawianie wersja QS
public:
AlgorytmySortowania(int LiczZbior):AISD(LiczZbior){};
~AlgorytmySortowania(){};
Parametry* PrzezSelekcje (int L=0,int R=0);
Parametry* PrzezWstawianie1(int L=0,int R=0); // podstawowa wersja algorytmu
Parametry* PrzezWstawianie2(int L=0,int R=0); // algorytm z jedna poprawka
Parametry* PrzezWstawianie3(int L=0,int R=0); // algorytm z dwiema poprawkami
Parametry* PrzezWstawianie4(int L=0,int R=0); // algorytm z dwiema poprawkami i poprawką wykładową
Parametry* PrzezWstawianie5(int L=0,int R=0); // algorytm z trzema poprawkami i poprawką wykładową
Parametry* Babelkowe (int L=0,int R=0);
Parametry* Shella (int L=0,int R=0);
Parametry* QuickSort (int L ,int R);
Parametry* QuickSortFactorM(int L ,int R,int M);
Parametry* QuickSortMediana(int L ,int R,int M);
};
R.1. sortowanie.h
Klasa AISD implementuje niezbędne metody operujące na strukturze danych, metody służące do pomiarów
czasu, wydruku raportów i komunikacji z użytkownikiem.
template
class AISD{
protected:
OBJ *Dane;
OBJ *DaneKopia;
int LicznoscZbioru;
Parametry ZA; //ZlozonoscAlgorytmu - Parametry
void OdswiezDane(); // przepisuje Dane_kopia do Dane
void ZA_Init(); // Inicjalizacja struktury danych ZA
long PobierzCzas();
inline void Zamien(OBJ &A,OBJ &B); // zamienia wartosci argumentow A i B
inline void ZamienWarunkowo(OBJ &A,OBJ &B); // zamienia wartosci argumentow gdy Bpublic:
AISD(int);
~AISD();
OBJ *GetDane();
OBJ *GetDaneKopia();
int GetLicznosc();
void Raport(char*);
void virtual ZapiszStanDoPliku(char*){}; //
void virtual WczytajDaneZPliku(char*){}; //implementacja IO zalezna od OBJ
void virtual WypiszStanNaEkran(bool){}; //
void virtual BadanieAlgorytmow(){}; //
};
R.2. aisd.h
Klasa AlgorytmySortowania składa się z części publicznej (public) i chronionej (protected). W publicznej części
klasy klasy szablonowej AlgorytmySortowania zadeklarowane są metody i zmienne bezpośrednio dostępne dla
użytkownika. Należą do nich wszystkie metody implementujące poszczególne algorytmy sortowania:
przez selekcje,
pięć wersji algorytmu sortowania przez wstawianie,
sortowanie bąbelkowe,
sortowanie Shella
trzy wersje algorytmu sortowania QuickSort.
W chronionej (protected) części klasy szablonowej AlgorytmySortowania zadeklarowano metody pomocnicze
dla zaimplementowanych algorytmów sortujących. Są to metody: Rozdziel, OdswiezDane, QuickSortRekur,
Zamien, ZamienWarunkowo, PobierzCzas, QuickSortRekurFactorM, QuickSortRekurMediana,
PrzezWstawianie2QS. Dla zapewnienia integralności danych Dane, ich wywołanie jest możliwe jedynie z
wnętrza obiektów tej samej klasy i klas pochodnych. Każda z metod sortowania na bieżąco aktualizuje
informacje przechowywane w strukturze kontrolnej ZlozAlg odziedziczonej po klasie macierzystej AISD. Po
zakończeniu pracy każda metoda sortowania zwraca wskaz
nik na strukturę kontrolną ZlozAlg (R.3):
1/5
Algorytmy i Struktury Danych
v.1/ 2009
typedef struct{
unsigned long CzWyk; // czas wykonania algorytmu
unsigned long GlSto; // biezaca glebokosc stosu
unsigned long GlStoMax;// maksymalna glebokosc stosu
unsigned long LiZam; // liczba zamian danych
unsigned long LiPor; // liczba porownan danych
} Parametry;
R.3. aisd.h
Każda z metod sortujących domyślnie zakłada, że dane do posortowania umieszczone są w tablicy wskazywanej
przez Dane: prywatny składnik szablonu klasy macierzystej AISD, inicjalizowany w czasie pracy jej
konstruktora. Argumentami wywołania poszczególnych metod sortowania są numery pierwszego (L) i ostatniego
(R) elementu początkowego zbioru danych do posortowania. Obecność tych parametrów w wywołaniu metody
umożliwia posortowanie całości lub wybranego fragmentu danych. Przy wywołaniu metod sortowania bez
podania argumentów domyślnie przyjmowane jest sortowanie pełnego zbioru danych o liczności LicznośćZbioru
(chroniony składnik klasy AISD). W publicznej części klasy AISD oprócz konstruktora i destruktora
zaimplementowano wirtualne metody umożliwiające operacje na plikach z danymi (ZapiszStanDoPliku i
WczytajDaneZPliku), a także wydruk tych danych na ekran (WypiszStanNaEkran). Ich argumenty to
odpowiednio: nazwa pliku do odczytu/zapisu danych i zmienna typu bool decydująca o wypisaniu lub nie
wypisaniu danych na ekran. Zdefiniowanie klas AISD i AlgorytmySortowania w postaci szablonów daje
możliwość zastosowania ich do operacji na różnych, w tym również złożonych typach danych określonych
parametrem OBJ szablonu. Wymaga to jedynie określenia typu tych danych (np. w postaci klasy, struktury,
tablicy, listy etc.) i odpowiedniego przeciążenia związanych z nim operatorów: porównania ( < i  > ) oraz
przypisania ( = ). AlgorytmySortowania to szablon klasy wirtualnej. Nie można więc utworzyć takiego obiektu.
Niezbędne jest więc zdefiniowanie klasy potomnej posiadającej własne wersje metod wirtualnych
WypiszStanNaEkran, ZapiszStanDoPliku i WczytajDaneZPliku. Dla potrzeb ćwiczenia utworzono klasy
AlgorytmySortowaniaINT i AlgorytmySortowaniaBI, pochodne szablonu klasy AlgorytmySortowania, utworzone
dla danych typu int i BiData (R.4).
class AlgorytmySortowaniaINT:public AlgorytmySortowania{
public:
AlgorytmySortowaniaINT(int LiczZbior):AlgorytmySortowania(LiczZbior){};
~AlgorytmySortowaniaINT(){};
void ZapiszStanDoPliku(char*);
void WczytajDaneZPliku(char*);
void WypiszStanNaEkran(bool);
void BadanieAlgorytmow();
};
class AlgorytmySortowaniaBI:public AlgorytmySortowania{
public:
AlgorytmySortowaniaBI(int LiczZbior):AlgorytmySortowania(LiczZbior){};
~AlgorytmySortowaniaBI(){};
void ZapiszStanDoPliku(char*);
void WczytajDaneZPliku(char*);
void WypiszStanNaEkran(bool);
void BadanieAlgorytmow();
};
R.4. sortowanie.h
Przykładową klasę BiData wykorzystaną jako argument szablonu klasy AlgorytmySortowania przedstawiono
wydruku R.5. Klasa ta jest przeznaczona do badania stabilności algorytmów sortowania.
class BiData{
public:
int i; // pole danych: klucz 1
char str[16]; // pole danych: klucz 2
BiData(); // konstruktor
BiData(int i,char *str); // konstruktor
void Set(int i,char *str);
int GetI();
char *GetStr();
bool operator<(BiData Dane); // przeciazony operator porownania
bool operator>(BiData Dane); // przeciazony operator porownania
BiData operator=(BiData Dane); // przeciazony operator przypisania
int operator=(int Dane); // przeciazony operator przypisania
char* operator=(char *Dane); // przeciazony operator przypisania
};
R.5. dane.h
W programie wykorzystywanym podczas ćwiczenia zaimplementowano przykładowe algorytmy sortowania dla
danych typów int i BiData. Wykorzystano tu odpowiednio obiekty SortINT i SortBI. SortINT to obiekt klasy
AlgorytmySortowaniaBI utworzonej z szabonu AlgorytmySortowania dla podstawowego typu danych int. SortBI
to obiekt klasy AlgorytmySortowaniaBI utworzonej z szablonu AlgorytmySortowania dla złożonego typu danych
BiData. Obiekty SortINT i SortBI są tworzone, inicjalizowane i wypełniane danymi w funkcjach
inicjalizujących: InitINT i InitBI. Losowe dane do posortowania są generowane przez funkcje Wypelnij_INT1 i
Wypelnij_BI1 (wydruk R.6).
void WypelnijINT_1(){
int i;
2/5
Algorytmy i Struktury Danych
v.1/ 2009
for(i=0;iGetLicznosc();i++)
SortINT->GetDaneKopia()[i]=(int)(rand()*(double)SortINT->GetLicznosc()/(double)RAND_MAX);
memcpy(SortINT->GetDane(),SortINT->GetDaneKopia(),SortINT->GetLicznosc()*sizeof(int));
}
void WypelnijBI_1(){
int i;
char (*stringi)[16]=new char[16][16];
strcpy(stringi[0],"A");
strcpy(stringi[1],"B");
strcpy(stringi[2],"C");
strcpy(stringi[3],"D");
strcpy(stringi[4],"E");
strcpy(stringi[5],"F");
strcpy(stringi[6],"G");
strcpy(stringi[7],"H");
strcpy(stringi[8],"J");
strcpy(stringi[9],"K");
strcpy(stringi[10],"L");
strcpy(stringi[11],"M");
strcpy(stringi[12],"N");
strcpy(stringi[13],"P");
strcpy(stringi[14],"R");
strcpy(stringi[15],"S");
for(i=0;iGetLicznosc();i++){
SortBI->GetDaneKopia()[i]=(int)(rand()*(double)SortBI->GetLicznosc()/(double)RAND_MAX);
SortBI->GetDaneKopia()[i]=stringi[rand()%15];
}
memcpy(SortBI->GetDane(),SortBI->GetDaneKopia(),SortBI->GetLicznosc()*sizeof(BiData));
delete stringi;
}
R.6. main.cpp
3. Przebieg ćwiczenia
Funkcja main (plik main.cpp, R.7) zawiera następujące parametry zadeklarowane w programie jako
zmienne globalne: Ekran  zarządza wypisywaniem danych na ekran), Srand  ustawia warunki początkowe dla
generatora liczb pseudolosowych (w trakcie ćwiczenia każdy student przypisuje tej zmiennej swój numer
albumu), FactorM  ustawia współczynnik przełączenia algorytmów w sortowaniu metodą QuickSort,
Licznosc  ustawia liczność zbioru do sortowania.
int main(){
Ekran=false;
Srand=10; //tu wpisz numer swojego albumu
FactorM=20;
Licznosc=1234;
try{
// InitINT();
// SortInt->BadanieAlgorytmow();
InitBI();
SortBI->BadanieAlgorytmow();
}
catch (Except e){ Error(e); }
getchar();
CleanUp();
return 1;
};
R.7. main.cpp
Dla wskazanych przez prowadzącego algorytmów sortowania (uzupełnić w notatniku) należy przystosować kod
przykładowego programu do zaplanowanych pomiarów i symulacji. Zależnie od wskazań prowadzącego należy
wykonać następujące czynności:
1. przeanalizować działanie poszczególnych algorytmów sortowania
2. zbadać złożoność obliczeniową wskazanych algorytmów sortowania,
3. określić stabilność wskazanych algorytmów sortowania,
4. przeanalizować możliwość stabilizacji badanych w ćwiczeniu niestabilnych algorytmów sortowania,
5. wskazać przyczyny potencjalnych ograniczeń wydajności badanych algorytmów sortowania
6. wskazać możliwe rozwiązania prowadzące do poprawy wydajności badanych algorytmów sortowania.
7. napisać procedury generujące różne rozkłady danych do sortowania.
8. dokonać analizy wydajności poszczególnych procedur sortowania w zależności od
a) długości serii sortowanych danych,
b) początkowego uporządkowania sortowanych danych,
9. eksperymentalnie dobrać optymalną wartość FactorM (metody QuickSortFactorM i
QuickSortMediana),
10. określić zależność wydajności algorytmu sortowania metodą Shella od rodzaju zastosowanego ciągu,
4. Analiza wyników, wnioski, sprawozdanie
3/5
Algorytmy i Struktury Danych
v.1/ 2009
Na ocenę z ćwiczenia bezpośrednio wpływają:
zawartość notatnika z ćwiczenia (w wersji papierowej) Na początku ćwiczenia należy wydrukować
umieszczony na końcu niniejszej instrukcji Notatnik. Będzie on stanowił bieżący zapis przebiegu ćwiczenia i
wyników pracy.
zawartość oddanego w terminie sprawozdania (wyłącznie w postaci elektronicznej w formacie pdf).
Sprawozdanie powinno zawierać następujące elementy:
cel ćwiczenia (własnymi słowami),
opis modyfikacji wprowadzonych do programu przykładowego wraz z analizą celowości tych zmian,
stosowne wykresy (np. wykresy czasów wykonania programu w zależności od wersji badanego
algorytmu w funkcji długości sortowanych danych, wykresy dynamiczne sortowania, czyli postęp
posortowania danych w zależności od liczby wykonanych kroków algorytmu sortującego& )
podsumowanie ćwiczenia czyli wnioski: konkretne, na temat, samodzielne, twórcze.
Na końcową ocenę za ćwiczenie składają się
sposób wykonania ćwiczenia,
samodzielność i pomysłowość w jego wykonaniu,
merytoryczna zawartość i forma i terminowość nadesłania sprawozdania.
Sprawozdanie powinno zostać nadesłane pocztą elektroniczną, w terminie podanym przez prowadzącego zajęcia
(zazwyczaj 7 dni). Pod rygorem nie sprawdzania sprawozdania dodatkowo niezbędne jest wypełnienie przez
studentów następujących wymogów formalnych:
jedyny przyjmowany format sprawozdania to PDF,
nazwa pliku zawierającego sprawozdanie musi spełniać wymogi wzorca AISDE_2_Nazwisko_Imie.pdf.
temat maila ze sprawozdaniem musi pasować do wzorca: AISDE_2_Nazwisko_Imie,
sprawozdania oddawane przez studentów muszą spełniać wymogi określone przez wykładowcę na
początku semestru.
Uwagi:
Do określenia liczby i rodzaju operacji wykonywanych w czasie sortowania należy wykorzystać strukturę
ZlozAlg.
Dla zapewnienia identycznych warunków pracy algorytmów sortujących w ramach danej serii pomiarowej,
do sortowania różnymi metodami powinny być wykorzystywane w zawsze te same dane wejściowe.
Po wygenerowaniu pomiarowej serii danych, dane te są przechowywane w zmiennej Dane_kopia.
Do sortowania wykorzystywane są dane przechowywane w zmiennej Dane.
Prywatna metoda OdswiezDane kopiuje dane ze zmiennej Dane_kopia do zmiennej Dane.
Miarodajny jest jedynie czas działania algorytmu sortowania a nie czas działania całej procedury z
uwzględnieniem operacji wypisania danych na ekran, czy ich zapisu na dysk.
Jednym z rodzajów wykresów wykonywanych w trakcie ćwiczenia są dynamiczne wykresy sortowania.
Przedstawiają one postęp procesu sortowania danych. Na osi rzędnych znajdują się kolejne numery pozycji
sortowanych danych, zaś na osi odciętych wartości odpowiadające kolejnym sortowanym danym.
Przykładowe wykresy dynamiczne przedstawiono na R.8.
a b c d e
R.8. Wykresy dynamiczne sortowania metodą QuickSort
Wymagania do kolokwium wstępnego:
znajomość badanych algorytmów sortowania
znajomość przykładowego programu (pełne kody z
ródłowe zamieszczone są na internetowej stronie
przedmiotu AISDE).
5. Literatura
1. R. Sedgevick  Algorytmy w C++ , Wydawnictwo RM, 1999,
2. J. Grębosz  Symfonia C++ Wydawnictwo Oficyna Kallimach 1997
3. J. Grębosz  Pasja C++ Wydawnictwo Oficyna Kallimach 1997
Opracowanie dr inż. Grzegorz Janczyk [e-mail]
Weryfikacja dr inż. Adam Wojtasik [e-mail]
4/5
Algorytmy i Struktury Danych
v.1/ 2009
NOTATNIK
Imię i nazwisko, Grupa dziekaoska Nr Indeksu Data wykonania dwiczenia Data oddania protokołu
Punkty do wykonania 1 2 3 4 5 6 7 8a 8b 9 10
Sortowanie przez selekcję
Sortowanie przez wstawianie 1
Sortowanie przez wstawianie 2
AISDE
Sortowanie przez wstawianie 3
Sortowanie przez wstawianie 4
LAB 2
Algorytmy do zbadania Sortowanie przez wstawianie 5
Sortowanie bąbelkowe
Sortowanie Shella
Sortowanie quick sort
Sortowanie quick sort factor-M
Sortowanie quick sort - mediana
Największa
Algorytm sortowania Stabilność Złożoność liczność zbioru Uwagi
testującego
NOTATNIK NALEŻY ODDAĆ PROWADZ
CEMU ZAJ
CIA W CHWILI ZAKOC
CZENIA ĆWICZENIA