WOJSKOWA AKADEMIA TECHNICZNA
IM. JAROSA
AWA D
BROWSKIEGO
Wydział Cybernetyki
Przedmiot:
Algorytmy i struktury danych
Laboratorium
SPRAWOZDANIE
Autor: ProwadzÄ…cy:
Adrian Kępa mgr inż. Jarosław Napiórkowski
Grupa: I3X6S1
1
Zadanie
Insertion Sort oraz Merge Sort  Porównanie algorytmów
Lista kroków
Insertion Sort
[1]Wczytaj dane z pliku do tablicy.
[2] Powtarzaj od i = 1 do (n  1) :
a) j = i.
b)Powtarzaj tak długo jak : j > 0 [AND] tablica[j] < tablica[j  1] :
c)Zamien miejscami elementy tablica[j] oraz tablica[j  1].
d)Dekrementuj j.
[3]Zamknij plik wynikowy.
[4]Koniec.
Merge Sort
[1]Wczytaj dane z pliku do tablicy.
[2]Rekurencyjnie dziel tablicÄ™ danych na dwa.
[3]Sortuj poszczegolne elementy scalajac je w podzbiory.
[4]Zapisuj do tablicy wynikowej posortowane elementy porównując zawartości podzbiorów z
zawartością tablicy wynikowej.
2
Schematy blokowe
Insertion Sort
3
Merge Sort
4
5
Kod z
ródłowy
Kody z
ródłowe przedstawianych algorytmów zostały załączone do sprawozdania w
oddzielnym folderze.
Doświadczenie
Przeprowadzono doświadczenie szybkości pracy omawianych algorytmów dla różnych ilości
danych do sortowania. Przedstawione czasy pracy dotyczą tylko i wyłącznie czasu trwania
funkcji sortujÄ…cej.
Do utworzenia tak licznych danych wejściowych, stworzono prosty generator liczb
pseudolosowych, zamieszczony razem z kodami z
ródłowymi programów sortujących.
Liczność zbioru do Czas pracy Insertion Sort [s] Czas pracy Merge Sort [s]
sortowania
10 000 0,165 0,004
20 000 0,589 0,008
40 000 2,331 0,010
80 000 10,095 0,021
160 000 40,762 0,043
320 000 154,024 0,093
640 000 633,370 0,192
1 000 000 1479,357 0,305
Wykres przedstawiony poniżej, przedstawia zależności czasu wykonania funkcji sortującej od
ilości danych do posortowania. Różowa łamana przedstawia zależność dla algorytmu
Insertion Sort, natomiast czerwona łamana algorytmu Merge Sort.Na tym wykresie widać
ogromną różnicę w czasie wykonania dla badanych algorytmów, czas łamana algorytmu
Merge Sort prawie pokrywa siÄ™ z osiÄ… OX podczas gdy Å‚amana algorytmu Insertion Sort
doskonale obrazuje szybkość wykładniczego wzrostu czasu pracy algorytmu.
6
Drugi wykres przedstawiony poniżej, przedstawia zależność czasu wykonania od ilości
danych dla algorytmu Insertion Sort.
Trzeci wykres poniżej, przedstawia zależność czasu wykonania od ilości danych dla
algorytmu Merge Sort.
7
Wnioski
Algorytm sortowania przez wstawianie jest algorytmem, który można intuicyjnie porównać
do wybierania losowych kart z talii i ręcznego sortowania ich. Wybieramy losową kartę i
porównujemy z drugim zbiorem który będzie zbiorem uporządkowanym. Na początku
oczywiście zbiór ten jest pusty, więc wstawiamy tam wylosowaną kartę. Następnie
wybieramy kolejną kartę ze zbioru pierwotnego i tym razem porównujemy z kartą w zbiorze
uporzÄ…dkowanym.
W ten sposób dokonuje się sortowania przez wybieranie  porównywanie wybranego
elementu z elementami już posortowanymi w drugim zbiorze. Złożoność obliczeniowa tego
algorytmu to O(n2) jednak zaletą tego algorytmu jest jego stabilność oraz wydajność w
przypadku gdy zbiór, który trzeba posortować jest wstępnie uporządkowany oraz mały.
Algorytm przez scalanie (merge sort) jest algorytmem, którego działanie polega na dzieleniu
zbioru wejściowego na dwa zbiory tak długo, aż otrzymamy same zbiory jedno elementowe.
Następnie dokonuje się scalania zbiorów jednocześnie sortując je. Dzięki temu dostajemy
zbiory wstępnie posortowane. Następnie łączy się zbiory tak długo aż wyczerpiemy wszystkie
podzbiory, otrzymujemy tym samym ostateczny posortowany zbiór.
Doświadczenie przeprowadzone dla tych algorytmów pozwoliło jednoznacznie wykazać, że
dla użytych danych, algorytm merge sort jest o wiele lepszy od algorytmu insertion sort.
Złożoność algorytmu insertion sort to O(n2) podczas gdy merge sort ma złożoność tylko
nÅ"log2 n
8
Gdyby zamieścić także wyniki czasu działania tych algorytmów dla ilości danych mniejszej
od 10 000, obydwa algorytmy widać by było również różnicę. Jednakże dla człowieka setne i
tysięczne części sekundy byłyby niezauważalne. Dlatego można stwierdzić, że dla małej
ilości danych do przetworzenia, wybór algorytmu jest w gruncie rzeczy nieistotny. Dopiero
gdy wymagane jest przetworzenie bardzo dużej ilości danych, należy zastanowić się nad
wyborem odpowiedniego algorytmu  Merge Sort jest jednym z najlepszych.
Zarówno sortowanie przez wstawianie jak i sortowanie przez scalanie są algorytmami
stabilnymi. Oznacza to, że elementy o takiej samej wartości ustawione są w takiej samej
kolejności w jakiej były ustawione w zbiorze pierwotnym  nie nastąpiła zamiana pomiędzy
elementami o tej samej wartości.
9