Mateusz GÄ…siorek 180514
Termin: Åšroda 16:10
SPRAWOZDANIE
Sortowanie  różne algorytmy, porównanie czasu pracy
Zaimplementowałem 4 algorytmy sortowania:
1) quickSort
2) sortowanie bÄ…belkowe ,
3) sortowanie przez kopcowanie,
4) sortowanie przez wstawianie.
Na wstępie opiszę po krótce sortowania:
1) Sortowanie szybkie  jeden z najpopularniejszych algorytmów sortowania. Jego działanie opiera się na
podzieleniu tablicy na dwie części, a następnie ułożeniu tych  połówek . Jego złożoność czasowa to
O(n log n).
2) Sortowanie bąbelkowe- prosta metoda sortowania o złożoności czasowej O(n2).
Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona
porządek, w jakim się sortuje tablicę. Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano
żadnej zmiany.
3) Sortowanie kopcem - zwane też inaczej sortowaniem przez kopcowanie. Algorytm ten jest jedną z
ciekawszych metod sortowania z racji faktu, iż jest on szybki oraz nie pochłania zbyt wiele zasobów
pamięci. Jego złożoność czasowa to O(n log n). Algorytm ten jest w praktyce z reguły nieco wolniejszy od
sortowania szybkiego, lecz ma lepszą pesymistyczną złożoność czasową (przez co jest odporny np. na atak
za pomocą celowo spreparowanych danych, które spowodowałyby jego znacznie wolniejsze działanie).
Sortowanie przez kopcowanie jest niestabilne, co może być czasami uznawane za wadę.
4) Sortowanie przez wstawianie - jeden z najprostszych algorytmów sortowania, którego zasada działania
odzwierciedla sposób w jaki ludzie ustawiają karty - kolejne elementy wejściowe są ustawiane na
odpowiednie miejsca docelowe. Jest efektywny dla niewielkiej liczby elementów, jego złożoność wynosi
O(n2). Posiada pewne zalety:
·ð jest wydajny dla danych wstÄ™pnie posortowanych
·ð jest wydajny dla zbiorów o niewielkiej liczebnoÅ›ci
·ð jest stabilny
W dalszej części pracy będę przeprowadzał sprawdzanie złożoności czasowej 4 algorytmów dla kilku
różnych wartości ilości elementów tablicy:
·ð 100,
·ð 200,
·ð 500,
·ð 1000,
·ð 2000,
·ð 5000,
·ð 10000,
·ð 50000,
·ð 100000.
Następnie sprawdzę jak dane algorytmy zachowują się w sytuacji kiedy elementy tablicy są ułożone:
·ð Od najwiÄ™kszego do najmniejszego,
·ð Od najmniejszego do najwiÄ™kszego,
·ð W kolejnoÅ›ci losowej,
·ð Gdy caÅ‚a tablica skÅ‚ada siÄ™ z jednakowych wartoÅ›ci.
Swoje wyniki przedstawiÄ™ w tabeli oraz na wykresach, na koniec wyciÄ…gne wnioski wskazujÄ…c najszybszy,
najwolniejszy algorytm sortowania dla danych wartości wejściowych.
Krótki opis pracy algorytmów:
1) Sortowanie szybkie
Jest to algorytm oparty na metodzie  dziel i zwyciężaj . W pierwszym kroku wybierany jest
element osiowy. Następnie wszystkie elementy tablicy dzielone są na dwie grupy: elementy
mniejsze od osiowego znajdujÄ… siÄ™ w pierwszej grupie, zaÅ› w drugiej znajdujÄ… siÄ™ elementy
równe bądz
większe. Element osiowy wstawiany jest na pozycję pomiędzy tymi dwoma
grupami. Następnie te dwie podgrupy dzielone są na kolejne, mniejsze podgrupy według
wybranych elementów osiowych. Czynność ta jest kontynuowana, do momentu, aż podgrupy
będą składały się z pojedynczego elementu.
2) Sortowanie bÄ…belkowe
Algorytm ten porównuje ze sobą dwie sąsiadujące wartości, zaczynając od ostatniej w tablicy.
Jeżeli zależność pomiędzy danymi nie jest zachowana, wówczas zamieniane są one ze sobą
miejscami.
3) Sortowanie kopcem
Jest to jedna z efektywnych metod sortowania, wykorzystujÄ…ca kopiec binarny. Z danych,
które mają zostać posortowane, budowany jest kopiec binarny. W korzeniu znajduje się
element, który zajmie pierwszą pozycję wśród posortowanych danych (najmniejszy w
przypadku sortowania elementów w porządku niemalejącym lub największy w przypadku
sortowania danych w porządku nierosnącym). Po usunięciu korzenia wywoływana jest
procedura przywracania własności kopca. Procedury usuwania korzenia i przywracania
własności kopca są kontynuowane do czasu, aż wszystkie dane zostaną posortowane.
4) Sortowanie przez wstawianie
Algorytm ten rozpoczyna działanie od porównania ze sobą dwóch pierwszych danych i
ustawienia ich w odpowiedniej kolejności. Następnie sprawdzana jest trzecia dana i
wstawiana jest na odpowiednią pozycję, spośród trzech pierwszych. Algorytm kontynuuje
działanie, aż wszystkie elementy zostaną wstawione na właściwą pozycję.
Swoje doÅ›wiadczenia przeprowadzam na systemie 32-bitowym Windows 7 pracujÄ…cym na Intel® Core"!2 Duo T5800 2.00GHz. Obliczenia wykonujÄ™ za pomocÄ…
programu DEV-C++ oraz bibliotek i funkcji zwiÄ…zanych z pomiarem czasu w milisekundach.
a) ELEMENTY UA
OŻONE LOSOWO
N (liczba Quick sort BÄ…belkowe Kopcowanie Wstawianie
Wykonano 3 razy Wykonano 3 razy Wykonano 3 razy Wykonano 3 razy
elementó
Wynik w [ms] Wynik w [ms] Wynik w [ms] Wynik w [ms]
w
tablicy)
100 0 0 0 0 0 1 0 0 0 0 0 0
200 0 0 0 0 1 1 0 0 0 0 0 0
500 0 0 0 5 6 4 0 0 0 0 0 0
1000 0 0 0 8 8 8 1 1 1 3 3 2
2000 1 1 1 35 34 33 1 1 1 8 9 9
5000 2 1 2 207 218 207 4 4 3 42 42 42
10000 5 4 4 863 840 831 6 7 6 168 170 169
50000 11 8 11 21084 21439 21237 19 17 16 4252 4228 4193
100000 18 22 18 87100 86839 86952 69 62 57 17041 16878 16858
b) ELEMENTY UA
OŻONE OD NAJMNIEJSZEGO DO NAJWI
KSZEGO
N (liczba Quick sort (mediana) BÄ…belkowe Kopcowanie Wstawianie
elementó Wykonano 3 razy Wykonano 3 razy Wykonano 3 razy Wykonano 3 razy
w Wynik w [ms] Wynik w [ms] Wynik w [ms] Wynik w [ms]
tablicy)
100 0 0 0 0 0 0 0 0 0 0 0 0
200 0 0 0 0 0 0 0 0 0 0 0 0
500 0 0 0 0 0 0 0 1 0 0 0 0
1000 0 0 0 0 0 0 1 1 0 0 0 0
2000 0 0 1 0 0 0 1 1 0 0 0 0
5000 1 1 1 0 0 0 3 3 2 0 0 1
10000 2 2 2 0 0 1 6 5 6 1 1 0
50000 4 6 6 1 1 0 31 33 33 1 2 2
100000 8 8 8 1 2 1 68 67 73 3 2 3
c) ELEMENTY UA
OŻONE OD NAJWI
KSZEGO DO NAJMNIEJSZEGO
N (liczba Quick sort (mediana) BÄ…belkowe Kopcowanie Wstawianie
elementó Wykonano 3 razy Wykonano 3 razy Wykonano 3 razy Wykonano 3 razy
w Wynik w [ms] Wynik w [ms] Wynik w [ms] Wynik w [ms]
tablicy)
100 0 0 0 0 0 0 0 0 0 0 0 0
200 0 0 0 0 0 1 0 0 0 0 0 1
500 0 0 0 3 3 3 0 0 0 1 1 1
1000 0 0 0 10 11 11 0 0 0 4 4 4
2000 0 0 0 44 43 45 0 0 1 17 16 17
5000 0 0 0 271 274 272 1 1 1 105 106 105
10000 1 1 1 1103 1144 1127 3 2 2 445 428 423
50000 5 5 5 28032 27832 28259 16 15 15 12018 13001 12153
100000 11 11 11 120067 121431 120943 32 33 34 44693 45590 44741
d) ELEMENTY SKA
ADAJ
CE SI
Z SAMEJ CYFRY 2
N (liczba Quick sort (mediana) BÄ…belkowe Kopcowanie Wstawianie
elementó Wykonano 3 razy Wykonano 3 razy Wykonano 3 razy Wykonano 3 razy
w Wynik w [ms] Wynik w [ms] Wynik w [ms] Wynik w [ms]
tablicy)
100 0 0 0 0 0 0 0 0 0 0 0 0
200 0 0 0 0 0 0 0 0 0 0 0 0
500 0 0 0 0 0 0 0 0 0 0 0 0
1000 0 0 0 0 0 0 0 0 0 0 0 0
2000 0 1 0 0 0 0 0 0 0 0 0 0
5000 1 1 1 0 0 0 0 1 0 1 0 0
10000 2 3 3 0 1 0 1 1 1 1 1 1
50000 15 16 14 1 1 0 2 2 1 2 1 1
100000 34 33 30 1 2 1 3 3 4 3 3 2
WYKRESY:
a) wersja bez skalowania, oraz ze skalowaniem osi Y dla lepszego widoku czasu trwania
100000
90000
80000
70000
Serie1
60000
Serie2
50000
Serie3
40000
Serie4
30000
20000
10000
0
1000
900
800
Serie1
700
Serie2
600
Serie3
500
Serie4
400
300
200
100
0
100 200 500 1000 2000 5000 10000 50000 100000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
5
0
1
2
5
0
0
0
1
5
0
1
b) oś Y wyskalowana do najdłuższego pomiaru
70
60
50
Serie1
40
Serie2
Serie3
30
Serie4
20
10
0
100 200 500 1000 2000 5000 10000 50000 100000
c) wersja bez skalowania, oraz ze skalowaniem osi Y dla lepszego widoku czasu trwania
120000
100000
80000
Serie1
Serie2
60000
Serie3
Serie4
40000
20000
0
100
90
80
70
Serie1
60
Serie2
50
Serie3
40
Serie4
30
20
10
0
100 200 500 1000 2000 5000 10000 50000 100000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
5
0
1
2
5
0
0
0
1
5
0
1
d) oś Y wyskalowana do najdłuższego pomiaru
40
35
30
25 Serie1
Serie2
20
Serie3
15
Serie4
10
5
0
100 200 500 1000 2000 5000 10000 50000 100000
Do pomiaru czasu w milisekundach (taki bowiem występuje we wszystkich pomiarach) użyłem biblioteki
oraz następującej funkcji:
StartTime= clock();
Funkcja_dla_której_ma_zliczać_czas_pracy;
StopTime=clock();
diff=(double)(StopTime-StartTime);
Wnioski:
Na podstawie podanych tabeli można wyciągnąć następujące wnioski:
- algorytm sortowania szybkiego niezależnie od ułożenia elementów w tablicy zachowuje się w sposób podobny
(wykonuje operacje szybko), jednak porówując go do innych to w momencie ustawienia elementów jednakowych na
tablicy algorytm ten wypada najwolniej.
- sortowanie bąbelkowe spełnia się tylko gdy tablica jest w  jakiś sposób posortowana, jeżeli natomiast wśród
elementów panuje  random algorytm ten znacznie wydłuża czas swojej pracy przez co staje się metodą
najwolniejszÄ…
- sortowanie przez kopcowanie wykonuje operacje również szybko, nawet gdy są one ułożone w odpowiedniej
kolejności, zajmuje natomiast jednak znacząco więcej pamięci, w momencie kiedy ułożone są min-max to
kopcowanie wypada najwolniejszym algorytmem
- sortowanie przez wstawianie sprawdza się dla małej ilości elementówi gdy są one ułożone w jakikolwiek sposób.
Algorytm ten okazał się natomiast prawie najwolniejszy w układaniu losowych elementów.
- na przedstawionych wykresach widać zależności w różnicach trwania czasu pracy algorytmu
- wykres pierwszy najciekawiej odzwierciedla najciekawszy (bo losowe wartosci w tablicy) przypadek. Doskonale na
nim widać jak  słabo w porównaniu do quicksorta wypadają inne algorytmy
PodsumowujÄ…c:
- algorytm quicksort można uznać za uniwersalny, który warto stosować nieznając zawartości tablicy
- kopcowanie również można uznać za algorytm uniwersalny (ze względu na krótki czas pracy nawet dla dużych
pomiarów tj.100 000)
- pozostałe algorytmy są dobre tylko gdy znamy zawartość tablicy. Użycie algorytmu bąbelkowego gdy tablica
ułożona jest odwrotnie jest złym pomysłem. Zajmuje to zbyt dużo czasu.