Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 2.4. Сортировка простым выбором 
public void SortSelection(int[] a) 
{ 
int N = a.Length; 
int min = 0, imin = 0, i; 
for (i = 0; i < N - 1; i++) 
{ 
min = a[i]; imin = i; 
// 
в этом цикле ищем минимальный элемент 
for (int j = i + 1; j < N; j++)
if (a[j] < min) 
{ 
min = a[j]; imin = j; 
} 
if (i != imin) 
{
// 
добавление нового элемента в отсортированную 
//
часть
a[imin] = a[i];
a[i] = min;
} 
} 
} 
20 / 23

---

21 
Обычно обмен местами двух элементов массива выполняется в три 
действия с использованием вспомогательной переменной. В данном примере 
роль вспомогательной переменной играет переменная min. Это несколько 
уменьшает время работы программы, так как доступ к простой переменной 
осуществляется быстрее, чем к элементу массива. 
Возможна довольно простая модификация данного алгоритма, преду-
сматривающая поиск в одном цикле просмотра одновременно минимума и 
максимума с последующим их обменом с первым и последним элементами 
неотсортированной части массива соответственно.
Скорость роста для данного алгоритма может быть определена, если 
найти зависимость числа C сравнений элементов и числа M их перестановок 
от размера массива. Число сравнений не зависит от исходной упорядоченно-
сти массива и определяется формулой 
(
)
2
1
1
1
~
2
2
i N
N N
N
C
i
= −
−
=
=

(2.1) 
в пределе больших N. 
В случае изначальной упорядоченности массива по возрастанию число 
перестановок минимально и М = N – 1. В случае, если изначально массив 
упорядочен по убыванию, число перестановок максимально и равно: 
(
)
(
)
/ 2
2 
0
14
(
2 ) 3
1
.
4
N n
i
N
N n
M
N
i
N
−
=
−
−
=
−
+
− =

(2.2) 
В этой формуле n = 3 для нечетных N и n = 4 для четных N. Детальный 
анализ, выполненный Д. Кнутом [24], приводит к следующему среднему зна-
чению M по всем возможным перестановкам элементов массива в пределе 
больших N:
(
)
2
~
,
ср
M
N log N
γ
+
(2.3) 
где 
γ – константа Эйлера. 
Суммируя значения C и M
ср
, получим, что среднее число операций при 
сортировке больших массивов методом простого выбора равно: 
(
)
2
2
2
2
~
.
2
2
N
N
N log N
Nlog N
γ
+
+
+
(2.4) 
В соответствии с правилом построения O-нотации, отбрасывая члены 
низшего порядка и числовые коэффициенты, получаем для данного алгорит-
ма сортировки скорость роста O(N
2
). 
21 / 23

---

22