blob: ad35f80e28819b8d807a4aa4ddec37a96ee23a21 (
plain)
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
|
\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}
|
