Методические указания. Одно из важнейших семейств методов сортировки основано на использовании следующей идеи: предполагается

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

Алгоритм сортировки методом простых вставок заключается в следующем. Пусть и записи a_1, …, a_j-1 уже размещены так, что . Будем сравнивать по очереди К_j c К_j-1, К_j-2, … до тех пор, пока не обнаружим, что запись a_j следует вставить между a_i и a_i+1; тогда подвинем записи a_i+1, …, a_j+1 на одно место вправо и поместим новую запись в позицию i+1.

Удобно совмещать операции сравнения и перемещения, перемежая их друг с другом. Поскольку запись a_j как бы “проникает на положенный ей уровень”, этот способ называют “просеиванием” или “погружением”.

Приведем пример сортировки массива из 5 чисел:

Исходный массив 5 2 4 1 3

Первое сравнение 5: 2

2 5: 4

2 4 5: 1

1 2 4 5: 3

Массив упорядочен 1 2 3 4 5

Знак “: ” означает сравнение. Стрелкой показана пересылка элемента.

Эффективность алгоритма зависит от числа сравнений и пересылок. Грубую оценку среднего числа сравнений можно произвести очень просто. Действительно, когда обрабатывается j-я запись, ее ключ сравнивается в среднем примерно с j/2 ранее отсортированными ключами; поэтому общее число сравнений приблизительно равно

(2.5)

Можно более точно оценить количество сравнений, используя понятие инверсии. Число проверок условий К_i< K_j зависит от числа инверсий в сортируемом множестве. Количество сравнений

(2.6)

где a_j – число инверсий (число элементов, больших К_j и стоящих слева от него).

Так число инверсий a_j и а_j связано с номером следующим соотношением:

Пусть независимы, тогда максимальное количество сравнений определяется формулой

(2.7)

Минимальное количество сравнений определяется формулой

(2.8)

где a_j = 0, т.е. массив упорядочен.

Среднее количество сравнений определяется из предположения, что среднее количество инверсий равно

(2.9)

Тогда среднее количество сравнений задается формулой

(2.10)

Усовершенствованиями метода простых вставок являются методы: бинарных вставок, двухпутевые вставки, метод Шелла, вставки в список и др. Познакомиться с этими методами и их сравнительными оценками можно по литературе.

Блок-схема данного метода представлена в Приложении 3.