Математическая логика и теория алгоритмов. Стенюшкина В.А. - 66 стр.

      Пример – Вход : (1,3,2, 4). Выход (1,2,3,4).
      Сортировка вставками для этого примера описывается последовательно-
стью: (1, 3, 2,4) => (1, 3, 2, 4) => (1, 2, 3, 4) =>(1, 2, 3, 4).
      Запишем в псевдокоде процедуру Sort_Ins, соответствующую сортировке
вставками
      Sort_Ins (А)
      1 for j←2 to length (A)
      2      do k ← A (j)
      3      i ← j-1
      4      while i > 0 and A (i) > k
      5          do A(i+1) ← A (i)
      6              i ← i-1
      7        A (i+1) ← k
      End {Sort_Ins}
      Здесь n = length (A), j – очередной элемент вставки; А (1 .. (j –1)) – отсор-
тированный участок, А ((j + 1) .. n) – осталось вставить; k – дублер элемента А
(j). Процедура работает следующим образом. В цикле for индекс j пробегает
массив слева направо. Извлекается элемент А(j) и вправо сдвигаются элементы,
большие его. Освободившееся место этот элемент и занимает. Обратим внима-
ние на то, что отступы соответствуют уровню вложенности операций.
      Под размером входа понимают либо общее число битов для его представ-
ления, либо числом стандартных параметров и т. д. В рассматриваемом приме-
ре размером входа будем считать размер сортируемого массива.
      Время работы можно определять числом элементарных шагов алгоритма,
хотя само понятие элементарного шага может каждый раз уточняться. Здесь
достаточно каждой строке псевдокода поставить в соответствие стоимость и
кратность. Общее время исполнения процедуры найдем умножением и сложе-
нием. Еще время уходит на вызов процедуры, но пока его не анализируем.
Имеем таблицу:

      Таблица 3.1

Номер строки        1      2        3        4        5          6          7

Стоимость           С1     С2       С3       С4       С5         С6         С7

                                             n        n          n
Кратность           n      n-1      n-1      ∑ tJ     ∑ (tj-1)   ∑ (tj-1)   n-1
                                             j=2      j=2        j=2

     Общее время Т(n)=с1n+с2(n-1)+с3(n-1)+с4∑tj+с5∑(tj-1)+с6∑(tj-1)+с7 (n-1); tj–
число раз исполнения строки 4, j =2..n.
     Если массив на входе уже отсортирован, то цикл в строке 4 завершается
после первой проверки. Общее время минимально: Т(n)=с1n+с2(n-1)+с3(n-1)+с4