Энциклопедия Turbo Pascal. Главы 1-4
Страница 7. Сортировка вставкой

Сортировка вставкой

     Сортировка вставкой является последней из класса простых ал-
горитмов сортировки. При сортировке вставкой сначала упорядочива-
ются два элемента массива.  Затем делается вставка третьего  эле-
мента   в  соответствующее  место  по  отношению  к  первым  двум
элементам. Затем делается вставка четвертого элемента в список из
трех  элементов.  Этот  процесс повторяется до тех пор,  пока все
элементы не будут упорядочены.  Например, для массива "dcab" сор-
тировка вставкой будет проходить следующим образом:
     - исходное состояние: d c a b;
     - первый проход:      c d a b;
     - второй проход:      a c d b;
     - третий проход:      a b c d.
     Ниже приводится алгоритм сортировки вставкой:

       { сортировка вставкой }
       procedure Inser(var item: DataArray; count:integer);
       var
         i, l: integer;
         x: DataItem;
       begin
         for i := 2 to count do
         begin
           x := item[i];
           j := i-1;
           while (x<item[j]) and (j>0) do
           begin
             item[j+1] := item[j];
             j := j-1;
           end;
           item[j+1] := x;

         end;
     end;  { конец сортировки вставкой }

     В отличие от сортировки пузырьковым методом и сортировки вы-
бором число операций сравнения для сортировки вставкой зависит от
исходной упорядоченности массива элементов.  Если исходный массив
уже  упорядочен,  то  число  операций  сравнения равно n-1.  Если
массив упорядочен в обратном порядке, то число операций сравнения
равно 1/2 (n**2 +n)-1,давая в среднем значение 1/4 (n**2+n-2).
     Число операций обмена будет следующим:
     - для лучшего случая: 2 (n-1);
     - в среднем: 1/4 (n**2+9n-10);
     - для худшего случая: 1/2 (n**2+3n-4).
     Таким образом,  число операций обмена для худшего случая бу-
дет столь же большим,  как и для сортировок пузырьковым методом и
сортировок выбором. Число операций обмена для среднего случая бу-
дет лишь на немного меньше.  Однако сортировка вставкой имеет два
преимущества. Во-первых, она обладает естественным поведением, т.
е.  она  выполняется  быстрее для упорядоченного массива и дольше
всего выполняется,  когда массив упорядочен в обратном  направле-
нии.  Это  делает  сортировку  вставкой полезной для упорядочения
почти отсортированных массивов. Во-вторых, элементы с одинаковыми
ключами  не  переставляются:  если список элементов сортируется с
использованием двух ключей, то после завершения сортировки встав-
кой он по-прежнему будет упорядочен по двум ключам.
     Несмотря на то,  что число сравнений может быть довольно не-
большим для определенных наборов данных, постоянные сдвиги масси-
ва требуют выполнения большого числа операций  пересылок. Однако,
сортировка вставкой имеет естественное поведение, требуя наимень-
шее число операций обмена для почти упорядоченного списка и  наи-
большее число операций обмена, когда массив упорядочен в обратном
направлении.