Маргинальные свойства простых сортировок целочисленных массивов
13
Последняя инструкция
a[i] = r
главного цикла — две операции —
устанавливает на место промежуточный минимум:
1 1
2,7
0
2 2 1 .
n
SortShift
i
W
n
Таким образом,
маргинальные свойства сортировки методом
сдвига
оцениваются суммированием числа операций на всех этапах:
2
1
min
2 min
9 10 3 ;
SortShift
SortShift
SortShift
W W W
n n
2
max
1
2 max
13 13
9
.
2 2
SortShift
SortShift
SortShift
W W W
n n
Сравнивая минимальные результаты сортировки, полученные ме-
тодом сдвига и модифицированным методом парных сравнений для
уже упорядоченного исходного массива, видим, что быстродействие
сортировки модифицированным методом парных сравнений превос-
ходит быстродействие сортировки методом сдвига:
2
min
min
9 10 3
2 6 .
SortShift
SortPairMod
W
n n W
n
В случае когда исходный массив упорядочен по убыванию,
быстродействие сортировки методом сдвига ниже, чем быстродей-
ствие сортировки методом выбора:
2
2
max
max
13 13
21 7
9
10
.
2 2
2 2
SortShift
SortChoice
W
n n W
n n
Сортировка методом последовательной вставки.
В алгоритме
возрастающей сортировки методом последовательной вставки преду-
смотрено, что упорядоченная часть находится в левой части массива,
а неупорядоченная — в правой. Начальный элемент из неупорядо-
ченной части вставляется на соответствующее место в упорядочен-
ной части. Продолжая итерации для начальных элементов всех
неупорядоченных частей, получаем отсортированный массив
a
.
В работе [3] исследованы свойства этого метода сортировки.
Обозначим минимальную оценку сортировки методом последова-
тельной вставки как
min
5 7 .
SortInsertSeq
W
n
Максимальная оценка этого метода
2
max
23 13
16
.
2 2
SortInsertSeq
W
n n
Сортировку методом последовательной вставки целесообразно
применять для
частично упорядоченных массивов
. Такая ситуация
наблюдается в случае, когда информационная система поддерживает
постоянно упорядоченный массив, в котором редко изменяются зна-
чения.
