2. Анализ алгоритмов 2.1. Сортировка вставками

Приступая к изучению анализа алгоритмов, мы рассмотрим достаточно простой алгоритм для задачи сортировки - сортировка методом включения. Напомним формулировка проблемы: Вход: последовательность n чисел (a1, a2,...,an) Выход: перестановка (aa1, aa2,...,aan) входной последовательности таким образом, что для всех ее членов выполняется соотношение aa1<=aa2<=...<=aan

В реальных задачах часто требуется сортировать не одни целые числа, а определенные значения, указывающие на, возможно, достаточно крупные структуры данных. Эти значения в таком случае называются ключами. Например, в базе данных о сотрудниках компании таким ключом может быть номер паспорта или водительских прав.

Алгоритм сортировки включением эффективно работает при сортировке небольшой количества элементов. Сортировка вставками напоминает способ, которым пользуются игроки для сортировки карт, что они имеют в своих руках. Пусть сначала в левой руке нет ни одной карты и все они лежат вниз. Далее со стола берется по одной карте, каждая из которых размещается в нужное для нее место среди уже избранных карт. Чтобы определить, куда нужно вставить новую карту, ее масть и вес сравниваются с мастью и весом карт в руке. Сравнение может проводиться, например, слева направо. В любой момент времени карты в руке будут отсортированы и это будут те карты, которые изначально лежали в бревне на столе.

Ниже приведен псевдокод методом включения под названием Insertion_sort. На его вход подается массив A [1 ... n], который содержит последовательность n чисел для сортировки (количество элементов здесь обозначена как length [A]). Входные числа сортируются без использование дополнительной памяти: их перестановка происходит внутри массива, а объем использованной для этого дополнительной памяти не превышает некоторую постоянную величину. По окончании работы алгоритма Insertion_sort входной массив будет содержать отсортированную последовательность.

На рис. 2.1 показано, как этот алгоритм работает для массива A = <5, 2, 4, 6, 1,3>. Элементы массива обозначены квадратиками, над которыми находятся индексы, а внутри - Значения соответствующих элементов. Части а - д этого рисунке соответствуют итерации цикла for в строках 1-8 псевдокода. В каждой итерации черный квадратик содержит значение ключа, которое сравнивается со значением серых квадратиков, расположенных слева от него (Строка 5). Серыми стрелками обозначены те значения массива, которые сдвигаются на одну позицию вправо (строка 6), а черной стрелкой - перемещение ключа (строка 8). В части е приводится заключительный состояние отсортированного массива. Индекс j указывает «текущую карту», ​​которая размещается в руке. В начале каждой итерации внешнего цикла for с индексом j массив A состоит из двух частей. Элементы A [1 ... j -1] соответствуют отсортированным картам в руке, а элементы A [j + 1 ... n] - колоде карт, которые остаются еще на столе. Заметим, что элементы A [1 ... j -1] с самого начала также находились на позициях от 1 до j -1, но в другом порядке, а теперь они отсортированы. Назовем это свойство элементов A [1 ... j -1] инвариантом цикла. Другими словами: в начале каждой итерации цикла for из строк 1-8 подмассив A [1 ... j -1] содержит те же элементы, которые были в нем с самого начала, но расположены в несортированный порядке.

Инварианты цикла позволяют понять, корректно работает алгоритм. Необходимо показать, что инварианты циклов обладают тремя следующим свойствами.

• Инициализация. Они выполняются перед первой инициализации цикла.
• Сохранение. Если они истинные перед очередной итерацией цикла, то они остаются истинными и после нее.
• Завершение. По окончании цикла инварианты позволяют убедиться в правильности алгоритма.

Если выполняются первые два свойства, инварианты цикла остаются истинными перед каждой очередной итерацией цикла. Можно заметить, что первые два свойства инвариантов цикла схожи с математической индукцией.

Рассмотрим, хранятся эти свойства для сортировки методом включения.

Инициализация. Покажем справедливость инварианта цикла для первой итерации, т.е. при j = 2. Таким образом, подмножество элементов A [1 ... j -1] состоит только из одного элемента A [1], который сохраняет исходное значение.

Сохранение. Покажем, что инвариант цикла сохраняется после каждой итерации. Можно сказать, что в теле внешнего цикла for происходит смещение элементов A [j -1], A [j -2], A [j -3] ... на одну позицию до тех пор, пока не освободится подходящее место для элемента A [j] (строки 4-7), куда он и располагается.

Завершение. Наконец, посмотрим, что происходит по завершению работы цикла. При сортировке методом включения внешний цикл for завершается, когда j больше n, то есть когда j = n + 1. Подставил в формулировки инварианта цикла значение n + 1, получим следующее утверждение: в подмножестве элементов A [1 ... n] находятся те же элементы, которые были в нем в начале работы алгоритма, но они расположены в отсортированном порядке. Это и подтверждает корректность алгоритма.