\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}