Маргинальные свойства простых сортировок целочисленных массивов
3
В максимальном случае на каждой итерации внутреннего цикла
затрачиваются три операции на проверку условия
a[j] < a[k]
и одна
операция на присваивание
k = j
:
1 1 1
1 1
2,4,3max
0 1
0
3 1
4
1 2 1 .
n n
n
SortChoice
i
j i
i
W
n i
n n
После окончания внутреннего цикла переменная
k
содержит индекс
текущего минимального элемента. Его значение необходимо перенести
в опорный элемент по индексу
i
. Для этого инструкция
int r = a[i]
запо-
минает значение
a[i]
— две операции. Инструкция
a[i] = a[k]
копирует
текущее минимальное значение
a[i]
в опорный элемент
a[k]
— три опе-
рации. Инструкция
a[k] = r
переносит прежнее значение опорного эле-
мента в освободившийся элемент
a[k]
— две операции. На всех итера-
циях главного цикла эти три инструкции перестановки значений
потребуют следующее количество операций:
1 1
2,5
0
2 3 2 7 1 .
n
SortChoice
i
W
n
Таким образом,
маргинальные свойства сортировки методом
выбора
оцениваются суммированием числа операций на всех этапах:
min
1
2 min
SortChoice
SortChoice
SortChoice
W
W
W
2
10 11
; 3
n n
max
1
2 max
SortChoice
SortChoice
SortChoice
W
W
W
2
21 7
10
.
2 2
n n
Сортировка методом перестановки.
Ниже представлена функ-
ция
SortExchange( )
, в которой позиция текущего упорядоченного
элемента заполняется очередным минимальным значением из неупо-
рядоченной части массива:
void SortExchange(int a[ ], const int n)
{ int n1 = n – 1;
for (int i = 0; i < n1; i++)
for (int j = i + 1; j < n; j++)
if (a[j] < a[i])
{ int r = a[i];
a[i] = a[j];
a[j] = r;
}
}
Интерфейс функции указывает адрес исходного неупорядоченно-
го массива
a
, содержащего
n
элементов. После выполнения функции
массив
a
упорядочен по возрастанию.
