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