1 files changed, 37 insertions, 0 deletions
diff --git a/reports/lab1/lab1.tex b/reports/lab1/lab1.tex
new file mode 100644
index 0000000..ad35f80
--- /dev/null
+++ b/reports/lab1/lab1.tex
@@ -0,0 +1,37 @@
+\documentclass[spec, och, labwork]{SCWorks}
+\usepackage{preamble}
+
+\begin{document}
+\include{titlepage.tex}
+
+\section*{Описание работы алгоритма}
+
+На $i$-м шаге выполнения алгоритма необходимо найти некоторый $k$-й наименьший
+элемент, где $i < k \leq n$, $n$ "--- размер массива. После того, как $k$-й
+элемент был найден необходимо поменять его местами с $i$-м элементом.
+
+Данный алгоритм необходимо повторить для каждого элемента массива. Таким образом
+будет получен массив, отсортированный по неубыванию.
+
+\subsection*{Оценка сложности}
+
+Нахождение минимального элемента в массиве требует проверки $n$ элементов
+($n - 1$ сравнений). Нахождение следующего минимального элемента потребует
+проверки $n - 1$ элементов ($n - 2$ сравнений). Таким образом, всего будет
+произведено следующее количество сравнений:
+\[ (n - 1) + (n - 2) + \ldots + 1 = \sum_{i = 1}^{n - 1} i \]
+
+Преобразуя данное выражение, получим
+\begin{equation*}
+    \sum_{i = 1}^{n - 1} i = \frac{(n - 1) + 1}{2} (n - 1) =
+    \frac{1}{2} n (n - 1) = \frac{1}{2} (n^2 - n)
+\end{equation*}
+
+Таким образом получаем, что алгоритм сортировки с помощью прямого выбора имеет
+алгоритмическую сложность $O(n^2)$ в среднем, лучшем и худшем случаях.
+
+\subsection*{Реализация на языке C++}
+
+\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{c}{../../straight-selection.cpp}
+
+\end{document}