1
УДК 681.3.06
Маргинальные свойства сортировки массивов
методом дихотомической вставки
©А.Ф. Деон, Ю.И. Терентьев
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
Выполнен сравнительный анализ маргинальных скоростных свойств сортировки
массивов методами последовательной и дихотомической вставки с учетом опера-
ций сравнения, сложения, перестановки и запоминания сортируемых элементов в
массивах целых чисел.
Ключевые слова:
сортировка, быстродействие, алгоритм, целые числа.
Сортировка массива методом последовательной вставки является
не самым быстродействующим способом упорядочивания массивов с
произвольными значениями [1], однако, когда массив частично упо-
рядочен, применение этого метода может дать более предпочтитель-
ные результаты. Для произвольного исходного массива он позволяет
воспользоваться дихотомическим поиском в упорядоченной части
массива. В этом случае метод сортировки с применением дихотомии
для определения места вставки дает лучшие результаты по быстро-
действию. Необходимо знать точные оценки выполненных операций
в различных условиях, среди которых крайние или маргинальные
оценки имеют особое значение.
Сортировка методом последовательной вставки.
Алгоритм
возрастающей сортировки методом последовательной вставки пола-
гает, что упорядоченная часть находится в левой части массива, а
неупорядоченная — в правой. Пусть начальный элемент
a
[0] исход-
ного массива
a
является единственным элементом упорядоченного
подмассива в левой части исходного массива. Это результат простого
утверждения, что одноэлементный массив является упорядоченным
массивом. Тогда неупорядоченная часть состоит из элементов
a
[1],
a
[2], …,
a
[
n
–1]. Запомним элемент
a
[1] из начала неупорядоченной
части в рабочей переменной
r = a
[1]. Затем осуществим вставку зна-
чения
r
в упорядоченную часть. Это возможно, поскольку элемент
a
[1] теперь свободен, а его значение скопировано в
r
. После вставки
получаются последовательности
r
,
a
[0] или
a
[0],
r
. Один из этих ва-
риантов находится теперь в элементах
a
[0],
a
[1]. После такой итера-
ции исходный массив содержит упорядоченную часть
a
[0],
a
[1] и
неупорядоченную —
a
[2],
a
[3], …,
a
[
n
–1]. Повторяя подобные дей-
ствия для неупорядоченного элемента
a
[2], получаем новые части
