УП_САОД_2003

Сортировка простым включением

В этой сортировке массив делится на 2 части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и «включается» в отсортированную часть массива.

Пусть отсортировано начало массива A[1], A[2], ..., A[i-1], а остаток массива A[i], ...,A[n] содержит неотсортированную часть. На очередном шаге будем включать элемент A[i] в отсортированную часть, ставя его на соответствующее место. При этом придется сдвинуть часть элементов, больших A[i], (если таковые есть) на одну позицию правее, чтобы освободить место для элемента A[i]. Но при сдвиге будет потеряно само значение A[i], поскольку в эту позицию запишется первый (самый правый – с самым большим индексом) сдвигаемый элемент. Поэтому прежде чем производить сдвиг элементов необходимо сохранить значение A[i] в промежуточной переменной.

Так как массив из одного элемента можно считать отсортированным, начнем с i=2.

Выглядит это в виде следующей процедуры.

procedure InsertSort(n: integer;

var A: array[1..n] of integer);

{Процедура сортировки простым включением}

var

i, j, Tmp: integer;

begin

for i := 2 to n do begin

{Сохраняем текущий элемент}

Tmp := A[i];

{Сдвигаем элементы, большие, чем текущий}

j := i-1;

while (A[j] > Tmp) and (j > 1) do begin

A[j+1] := A[j];

j := j-1;

end;

{Вставляем текущий элемент}

A[j+1] := Tmp;

end;

Рисунок 41. Сортировка простым включением

Этот алгоритм также имеет максимальную и среднюю временную сложности, пропорциональные O(n²), но в случае исходно отсортированного массива внутренний цикл не будет выполняться ни разу, поэтому метод имеет временную сложность T_min(n), пропорциональную O(n). Можно заметить, что метод использует любой частичный порядок, и чем в большей степени массив исходно упорядочен, тем быстрее он закончит работу. В отличие от предыдущего метода, этот не требует дополнительной памяти, но сохраняет порядок элементов с одинаковыми значениями.

Содержание