Метод вставки
Метод основывается на
следующем: считается, что перед рассмотрением записи 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
