Программы •Железо • Драйверы • Хостинг •Энциклопедия рекламы

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

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