Задача сортировки состоит в том, чтобы упорядочить
$N$ объектов $a_1, ... , а_N$, переставить их в такой последовательности
$а_{p1} , ..., a_{pN}$, чтобы их ключи расположились в неубывающем
порядке: $k_{p1} ≤ k_{p2} ≤ ... ≤ k_{pN}.$
Сортировка называется устойчивой, если она удовлетворяет условию, согласно которому записи с одинаковыми ключами остаются в прежнем порядке
Разделим условно все элементы массива на две последовательности: входную
$a_i, ... , а_N$ и готовую последовательность $a_1, ... , а_{i-1}$ элементы которой уже отсортированы. В алгоритмах, основанных на методе включения, на каждом i-м шаге i-й элемент входной последовательности вставляется в подходящее место готовой последовательности.
Сортировка простыми включениями наиболее очевидна.
Пусть 2 < i < N, $a_1, ... , а_{i-1}$ уже отсортированы:$a_1 ≤ а_2 ≤ ... ≤ a_{i-1}$.
Будем сравнивать по очереди $а_i$ с $a_{i-1}$, $а_{i-2}$, ... до тех пор, пока не
обнаружим, что элемент $а_i$ следует вставить между $a_j$ и $a_{j+1}$ (0 ≤ j ≤ i-1)
После этого или в процессе поиска подвинем записи $a_{j+1}$, ..., $a_{i-1}$ на
одно место вправо и переместим запись $а_i$ в позицию j + 1.
Условно разделить массив A на отсортированную и
несортированную части. К сортированной части сначала
относится только первый элемент.
цикл по i от 2 до N с шагом 1 выполнять
// i – номер первого элемента в несортированной части массива
x:= A[i];
j := i – 1;
// Все элементы из отсортированной части, большие,
// чем x, сдвинуть на одну позицию вправо:
пока j>0 и A[j]>x выполнять
A[j+1] := A[j];
j := j – 1;
конец пока
// Элемент x поставить на свое место по порядку:
A[j+1] := x;
конец цикла
На i-м шаге максимально возможное число сравнений $С_i$ во внутреннем цикле равно i -1;
если предположить, что все перестановки N ключей равновероятны, число сравнений в среднем равно i/2.
Для $M_i$, количества пересылок на i-м шаге,
максимальное $М_i = С_i + 2.$
Всего шагов N - 1.
Следовательно, количество сравнений и пересылок в худшем и лучшем случаях:
p.s. Тут кажется Нестеренко напутала М_мах
Наихудшим случаем является массив, отсортированный в порядке, обратном нужному. При этом каждый новый элемент сравнивается со всеми в отсортированной последовательности.