Учебно-методическое пособие. Алматы, 2017 ббк

3.1.3. Сортировка вставками

Все сортировки, рассмотренные выше, требуют (N! - N)/2 операций сравнения. Используя дихотомический поиск, количество операций сравнения можно сократить.

Будем просматривать элементы массива А, начиная со второго. Каждый новый элемент А[i] будем вставлять на подходящее место в уже упорядоченную совокупность А[1], ...А[i - 1]. Это место определяется последовательными сравнениями элемента А[i] с упорядоченными элементами А[1], ...А[i - 1].

Такой метод сортировки называется сортировкой простыми вставками. Для вставки элемента в нужное место все элементы, стоящие за ним, сдвигаем до позиции, которую занимал вставляемый на данном шаге элемент.

Сортировка вставкой является последней из класса простых алгоритмов сортировки. При сортировке вставкой сначала упорядочиваются два элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первым двум элементам. Затем делается вставка четвертого элемента в список из трех элементов. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены. Например, для массива "dcab" сортировка вставкой будет проходить следующим образом:

- исходное состояние: d c a b;

- первый проход: c d a b;

- второй проход: a c d b;

- третий проход: a b c d.

Ниже приводится алгоритм сортировки вставкой:

var

x: DataItem;

begin

for i := 2 to count do

x := item[i];

j := i-1;

while (x0) do

begin

item[j+1] := item[j];

end;

end; { конец сортировки вставкой }

Число операций обмена будет следующим:

- для лучшего случая: 2 (n-1);

- в среднем: 1/4 (n**2+9n-10);

- для худшего случая: 1/2 (n**2+3n-4).

Таким образом, число операций обмена для худшего случая будет столь же большим, как и для сортировок пузырьковым методом и сортировок выбором. Число операций обмена для среднего случая будет лишь на немного меньше. Однако сортировка вставкой имеет два преимущества. Во-первых, она обладает естественным поведением, т. е. она выполняется быстрее для упорядоченного массива и дольше всего выполняется, когда массив упорядочен в обратном направлении. Это делает сортировку вставкой полезной для упорядочения почти отсортированных массивов. Во-вторых, элементы с одинаковыми ключами не переставляются: если список элементов сортируется с использованием двух ключей, то после завершения сортировки вставкой он по-прежнему будет упорядочен по двум ключам.

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

1. Написать программу сортировка вставками. Провести трассировку программы для трех случаев:

а) первоначальный массив достаточно хорошо упорядочен.

б) первоначальный массив произвольный.

в) первоначальный массив упорядочен в обратном направлении.

Оценить время работы программы для массива с 10 000 элементами.

2. Сравнитьвремя работы программы с временем работы программ SortSH.