Added latex school projectHEADmaster

1 files changed, 235 insertions, 0 deletions

diff --git a/LaTeX/Statistical analysis of sorting algorithms/Statistical analysis of sorting algorithms.tex b/LaTeX/Statistical analysis of sorting algorithms/Statistical analysis of sorting algorithms.tex
new file mode 100644
index 0000000..a1bc385
--- /dev/null
+++ b/LaTeX/Statistical analysis of sorting algorithms/Statistical analysis of sorting algorithms.tex
@@ -0,0 +1,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}