1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
|
% Document must be built with XeLaTeX
% License and source at https://github.com/Syndamia/latex-projects
\documentclass[12pt,a4paper]{article}
\usepackage{pgfplots}
\pgfplotsset{height=8cm, width=10cm}
\usepackage{fontspec} % loaded by polyglossia, but included here for transparency
\usepackage{polyglossia}
\setmainlanguage{russian} % alternative for lack of bulgarian support
\setotherlanguage{english}
\addto\captionsrussian{
\renewcommand{\contentsname}{Съдържание}
\renewcommand{\refname}{Източници}
}
\newfontfamily\russianfont{Times New Roman}
\bibliographystyle{plain}
\title{Статистическо изследване върху алгоритми за сортиране}
\author{Камен Димитров Младенов}
\date{23 Януари 2021}
\begin{document}
\maketitle
\begin{center}
{\fontsize{10pt}{4}\selectfont https://github.com/Syndamia/latex-projects/tree/main/Statistical\%20analysis\%20of\%20sorting\%20algorithms}
\end{center}
\tableofcontents
\newpage
\section{Същност и избор на темата}
Сортиращият алгоритъм е един от най-важните аспекти на програмирането в днешно време.
Чрез него, дадени елементи могат да бъдат подредени в нарастваща (или намаляваща) последователност, което намира употреба във всичко от новинарски сайтове и социални медии, до видео игри и операционни системи.
Този тип алгоритъм бива изследван практически от началото на компютърната наука - най-ранните сортиращи алгоритми се забелязват през 1951, а анализиране на Bubble Sort, може би най-известния сортиращ алгоритъм, бива извършено още през 1957.\cite{wikipedia_sorting_algorithm_history}
В днешно време има десетки и стотици алгоритми, което дълбоко усложнява изборът на обикновения програмист.
Затова тази статия се стреми да сравни главните им характеристики.
\section{Избор на алгоритми и разглеждани харакетристики}
Избраните алгоритми за сравнение са подбрани от Toptal\cite{toptal}. Този сайт не е в никакъв случай решаващо място за най-известни алгоритми, но за целите на този документ е достатъчен.
Избраните алгоритми са:
\begin{itemize}
\item Shell Sort
\item Merge Sort
\item Heap Sort
\item Quick Sort
\end{itemize}
Данни относно характеристиките им ще бъдат взети от Toptal\cite{toptal} и от warp.povusers.org\cite{comparing_algorithms}. Отново, тези сайтове не са решаващи източници на която и да е от данните, но са достатъчни.
Избрани характеристики:
\begin{itemize}
\item Сложност
\item Скорост
\item Брой сравнения
\item Брой записвания
\end{itemize}
\newpage
\section{Представителна извадка}
Разглеждайки дадените източници, можем да извадим следните стойности:
\begin{center}
\begin{tabular}{|c|c c c c|}
\hline
Име на алгоритъм & Сложност & Скорост & Брой сравнения & Брой записвания \\[3pt]
\hline\hline
Shell Sort & 6666 & 0.71 & 101319 & 136506 \\[3pt]
Merge Sort & 18494 & 0.67 & 56823 & 70000 \\[3pt]
Heap Sort & 18494 & 0.59 & 107688 & 171318 \\[3pt]
Quick Sort & 18494 & 0.60 & 95321 & 42888 \\[3pt]
\hline
\end{tabular}
\end{center}
Важни бележки отностно вземането на тези данни:
\begin{itemize}
\item сложността е изчислена при горната граница (O) с 5000 елемента
\item скоростта, броят сравнения и броят записвания са взети при сравнение на 5000 случайно разбъркани целочислени числа с минимални повторения помежду им\cite{comparing_algorithms}
\item скоростта (както записано в warp.povusers.org\cite{comparing_algorithms}) е в милисекунди
\item в ситуации на неизвестна или променлива абсолютна максимална сложност, се използва тази сложност, която дава най-висока стойност
\end{itemize}
\section{Статистика на данните}
Снабдени с данни, вече можем да правим статистически анализ върху тях. Следващите подраздели показват с таблици и диаграми различни свойства и съотношения на тази информация.
\subsection{Вариационни редове}
\begin{center}
\begin{tabular}{|c|c c c c|}
\hline
& Shell sort & Merge Sort & Heap Sort & Quick Sort \\[3pt]
Сложност & 6666 & 18494 & 18494 & 18494 \\[3pt]
\hline\hline
& Heap sort & Quick Sort & Merge Sort & Shell Sort \\[3pt]
Скорост & 0.59 & 0.60 & 0.67 & 0.71 \\[3pt]
\hline\hline
& Merge sort & Quick Sort & Shell Sort & Heap Sort \\[3pt]
Брой сравнения & 56823 & 95321 & 101319 & 107688 \\[3pt]
\hline\hline
& Quick sort & Merge Sort & Shell Sort & Heap Sort \\[3pt]
Брой записвания & 42888 & 70000 & 136506 & 171318 \\[3pt]
\hline
\end{tabular}
\end{center}
\subsection{Мода, медиана, средна стойност}
\begin{center}
\begin{tabular}{|c|c c c|}
\hline
Характеристика & Мода & Медиана & Средна стойност\\[3pt]
\hline\hline
Сложност & 18494 & $(18494 + 18949)/2 = $\underline{$18494$} & 15537 \\[3pt]
Скорост & Няма & $(0.60+0.67)/2 = $\underline{$0.635$} & 0.6425 \\[3pt]
Брой сравнения & Няма & $(95321 + 101319)/2 = $\underline{$98320$} & 90287.75 \\[3pt]
Брой записвания & Няма & $(70000 + 136506)/2 = $\underline{$103253$} & 105178 \\[3pt]
\hline
\end{tabular}
\end{center}
\subsection{Сравнение на данни}
\begin{center}
\begin{tikzpicture}
\begin{axis}
[
ybar,
enlargelimits=0.15,
ylabel={\ Сложност},
xlabel={\ Алгоритъм},
symbolic x coords={Shell, Merge, Heap, Quick},
xtick=data,
nodes near coords, % this command is used to mention the y-axis points on the top of the particular bar.
nodes near coords align={vertical},
]
\addplot coordinates {(Shell,6666) (Merge,18494) (Heap,18494) (Quick,18494) };
\end{axis}
\end{tikzpicture}
\textbf{Диаграма 1: Сравнение на сложност}
\begin{tikzpicture}
\begin{axis}
[
ybar,
enlargelimits=0.15,
ylabel={\ Скорост (в милисекунди)},
xlabel={\ Алгоритъм},
symbolic x coords={Shell, Merge, Heap, Quick},
xtick=data,
nodes near coords, % this command is used to mention the y-axis points on the top of the particular bar.
nodes near coords align={vertical},
]
\addplot coordinates {(Shell,0.71) (Merge,0.67) (Heap,0.59) (Quick,0.60) };
\end{axis}
\end{tikzpicture}
\textbf{Диаграма 2: Сравнение на скорост}
\begin{tikzpicture}
\begin{axis}
[
ybar,
enlargelimits=0.15,
ylabel={\ Брой сравнения},
xlabel={\ Алгоритъм},
symbolic x coords={Shell, Merge, Heap, Quick},
xtick=data,
nodes near coords, % this command is used to mention the y-axis points on the top of the particular bar.
nodes near coords align={vertical},
]
\addplot coordinates {(Shell,101319) (Merge,56823) (Heap,107688) (Quick,95321) };
\end{axis}
\end{tikzpicture}
\textbf{Диаграма 3: Сравнение на брой сравнения}
\begin{tikzpicture}
\begin{axis}
[
ybar,
enlargelimits=0.15,
ylabel={\ Брой записвания},
xlabel={\ Алгоритъм},
symbolic x coords={Shell, Merge, Heap, Quick},
xtick=data,
nodes near coords, % this command is used to mention the y-axis points on the top of the particular bar.
nodes near coords align={vertical},
]
\addplot coordinates {(Shell,136506) (Merge,70000) (Heap,171318) (Quick,42888) };
\end{axis}
\end{tikzpicture}
\textbf{Диаграма 4: Сравнение на брой записвания}
\end{center}
\section{Заключение и анализ на резултатите}
Получената информация дава интересен, но дълбоко непълен, поглед към ефикасността на тези четири алгоритъма.
Разбира се, данните са събрани при само един тест в само една ситуация, затова каквото заключение да направим, то не бива да бъде взето за дадено.
Quick Sort не е най-бързият алгоритъм, макар и думата "бърз" да фигурира в името му. Тази титла взема Heap Sort, който има същата сложност, обаче му трябват повече сравнения и записвания.
Интересно наблюдение е как сложността на Shell Sort е почти три пъти по-малка от другите три алгоритъма, ала изисква най-много сравнения и записвания, и е вторият по бавност.
Обаче, в края на деня, се забелязва най-важното нещо: всеки алгоритъм има своя роля. Най-прост е Shell, най-бърз е Heap, най-малко сравнения ползва Merge и най-малко записвания прави Quick.
Правилния начин на избор на един от тези алгоритми е анализирането на ситуацията, в която той ще бъде използван.
Но, все пак, бих желал да отбележа, че не можеш да сгрешиш, ако ползваш Quick Sort.
Той се класира на второ или първо място във всички разглеждани категории, а в много от тези, които не сме разглеждали, той побеждава всяка конкуренция!
\newpage
\nocite{*}
\bibliography{sources}
\end{document}
|
