Методы вставки. Алгоритм простых вставок.

Билет №5. Метод вставок.

Метод вставки

Метод основывается на следующем: считается, что перед рассмотрением записи R[j] предыдущие записи R[1], R[2],..., R[j-1] уже упорядочены, и R[j] вставляется в соответствующее место. Сортировка таблицы начинается со второй записи. Ее ключ сравнивается с ключом первой записи, и, если упорядоченность
нарушена, то записи R[1] и R[2] переставляются. Затем ключ записи R[3] сравнивается с ключами записей R[2] и R[1]. На j - м шаге К[j] сравнивается по очереди сK[j-1], K[j-2],...(K[1]< =K[2]< =...< =K[j-1]) до тех пор, пока выполняется условие K[j]< K[i] (i=j-1, j-2,...) или достигнут левый конец упорядоченной подтаблицы (i=1, K[j]< K[1]). Выполнение условия K[j]> =K[i] означает, что запись R[j] нужно вставить между R[i] и R[i+1]. Тогда записи R[i+1], R[i+2],..., R[j-1] сдвигаются на одну позицию, и запись R[j] помещается в позицию i+1.
Операции сравнения и перемещения записей удобно совмещать, перемежая их друг с другом (этот способ называется " просеиванием").
Ниже показано выполнение j-го шага сортировки (с " просеиванием").

5 8 10 14 6 2 11 ¦ j=5, i=4, 6 < 14
< -~~ ¦
5 8 10 6 14 2 11 ¦ i=3, 6 < 10
< -~~ ¦
5 8 6 10 14 2 11 ¦ i=2, 6 < 8
< -~~ ¦
5 6 8 10 14 2 11 ¦ i=1, 6 > 5

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

n * (n - 1)
C = ------------
4
При достаточно большом числе элементов в сортируемой таблице можно принять C = n**2/4. Максимальное количество перестановок при использовании этого метода примерно равно n**2/4
Метод вставки обычно используется тогда, когда записи вносятся в упорядоченную таблицу. Новая запись должна быть вставлена в таблицу таким образом, чтобы существующая упорядоченность не нарушалась.

Модифицированный метод вставки (бинарное включение)

Метод прямого включения можно улучшить, если вставлять очередной элемент таблицы в упорядоченную подтаблицу с помощью метода бинарного (дихотомического, двоичного, логарифмического) поиска.
j-й шаг сортировки:

5 6 8 10 14 18 9 2 ¦ i = 6/2 = 3; 9 > 8
~~~~~~ ~~~~~~~~~ ~~ ¦
отбрасывается рассматривается ¦
-- ¦
... 10 14 18 9 2 ¦ i = (4+6)/2 = 5;
~~ ~~~~~ ¦ 9 < 14
рассм. отбрас. ¦
¦
... 9 10 14 18 2 ¦ i = 4; 9 < 10

Методы вставки. Алгоритм простых вставок.

Ниже описан основной алгоритм простых вставок, который порождает несколько модификаций, используемых в заданиях. Алгоритм использует прием, которым пользуются игроки в карты при сортировке только что розданной колоды: очередная карта вставляется между уже упорядоченными ранее. Описание алгоритма простых вставок. Файл, подлежащий сортировке, в общем случае состоит из элементов-записей, включающих информационную часть и ключи, по которым производится упорядочение по возрастанию. Поскольку информационная часть почти не влияет на процесс сортировки, будем предполагать, что файлы, используемые в примерах, состоит только из элементов-ключей, а информационная часть записи отсутствует. Здесь k[1], k[2],..., k[N] - ключи, по которым производится упорядочение файла. X, i, j - рабочие переменные.

Для примера возьмем файл, состоящий из 8 элементов:
Исх.файл.: 503 87 512 61 908 170 897 275
Алгоритм будет преобразовывать его следующим образом:
j=2. Исх: 503 87 X=87
Рез: °87 503

j=3: 87 503 °512 X=512
j=4: °61 87 503 512 X=61
j=5: 61 87 503 512 °908 X=908
j=6: 61 87 °170 503 512 908 X=170
j=7: 61 87 170 503 512 °897 908 X=897
j=8: 61 87 170 °275 503 512 897 908 X=275
Время работы алгоритма t примерно оценивается формулой:
t=a*N + b*N, где a, b - неизвестные константы, зависящие от программной реализации алгоритма.