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