Знакомая идея: раздвинуть карты в руке

Мы уже разобрали два способа: выбором — найти минимум в хвосте и поставить в начало, и пузырьком — менять соседей, пока большие не всплывут к концу. Оба переставляют элементы перестановками через соседние или дальние пары. Теперь посмотрим на третий способ, который устроен иначе и, пожалуй, ближе всего к тому, как мы сами упорядочиваем что-то в быту.

Вспомним, как берут карты в руки. Первая карта кладётся как есть. Вторая берётся в руку, сравнивается с первой и вставляется либо перед ней, либо после — так, чтобы маленькая карта оказалась слева, большая справа. Третья карта берётся и вставляется в уже упорядоченный ряд из двух карт на подходящее место. Каждая новая карта «находит» своё место в уже отсортированной части, раздвигая соседей. То же самое делает сортировка вставками с массивом.

Формально: пусть первые i элементов уже упорядочены. Возьмём элемент a[i] — он ещё не входит в отсортированный префикс. Сохраним его отдельно: это key. Дальше двигаемся по префиксу справа налево: сравниваем a[j] с key, и если a[j] больше, сдвигаем a[j] на позицию вправо — a[j+1] = a[j] — и уменьшаем j. Как только нашли элемент, который не больше key, или дошли до начала массива, кладём key на освободившееся место: a[j+1] = key. Префикс увеличился на один, по-прежнему оставаясь упорядоченным.

Обе детали принципиальны, и разберём их по отдельности.

Первая: key сохраняется в отдельную переменную. Зачем? Потому что при сдвигах мы перезаписываем a[i] — на его место встаёт a[i−1], если тот больше. Если бы мы не сохранили a[i] заранее, значение потерялось бы, и вставлять было бы нечего.

Вторая: сдвиг идёт справа налево. Если бы мы пошли слева направо, то на позицию j+1 положили бы a[j], но при следующем шаге нам понадобилось бы a[j+1] — а оно уже затёрто. Мы бы потеряли то, что ещё предстояло сдвинуть. Справа налево такого не происходит: прежде чем сдвинуть a[j] вправо, мы знаем, что позиция j+1 уже свободна — либо она была исходной позицией key, либо освобождена предыдущим сдвигом.

Полезно связать это с тем, что мы делали в уроке 2.1, когда освобождали место для вставки в массив: там мы тоже сдвигали хвост вправо. Разница в том, что здесь мы не создаём новых элементов и не расширяем массив — мы работаем с уже имеющимися, раздвигая их внутри себя. Сортировка вставками — это последовательность таких «освобождений места» на растущей длине: от одного элемента префикса до n.

Инвариант, трассировка и программа

Сформулируем инвариант. В начале итерации внешнего цикла (с номером i) элементы a[0..i) уже отсортированы по неубыванию, а элементы a[i..n) ещё не тронуты. После завершения итерации элементы a[0..i+1) отсортированы, а a[i+1..n) не тронуты. То есть отсортированный префикс растёт на один элемент за итерацию, и когда i доходит до n, весь массив упорядочен.

Во время сдвигов инвариант временно нарушается: в массиве может появиться дубликат одного и того же значения, потому что мы перезаписали a[j+1] значением a[j], не изменив исходное a[j]. Это нормальное промежуточное состояние: key живёт в отдельной переменной, и как только найдено место, дубликат исчезает — key кладётся на освободившуюся позицию, а прежний a[j+1] уже переехал. Кратности сохраняются после завершённой вставки, хотя на промежуточных шагах картина может выглядеть странно.

Прогоним на массиве [5, 2, 4, 6, 1, 3]. Первый элемент 5 уже отсортирован — префикс длины один.

Вставка i = 1, key = 2. j = 0: a[0] = 5 > 2, сдвигаем: a[1] = 5. j = −1, выходим из цикла, кладём a[0] = 2. Массив стал [2, 5, 4, 6, 1, 3]. Префикс [2, 5].

Вставка i = 2, key = 4. j = 1: a[1] = 5 > 4, сдвигаем: a[2] = 5. j = 0: a[0] = 2 > 4? Нет. Кладём a[1] = 4. Массив [2, 4, 5, 6, 1, 3]. Префикс [2, 4, 5].

Вставка i = 3, key = 6. j = 2: a[2] = 5 > 6? Нет. Кладём a[3] = 6. Массив не изменился.

Вставка i = 4, key = 1. j = 3: a[3] = 6 > 1, сдвигаем: a[4] = 6. j = 2: a[2] = 5 > 1, сдвигаем: a[3] = 5. j = 1: a[1] = 4 > 1, сдвигаем: a[2] = 4. j = 0: a[0] = 2 > 1, сдвигаем: a[1] = 2. j = −1, выходим. Кладём a[0] = 1. Массив [1, 2, 4, 5, 6, 3]. Заметьте: единица прошла через четыре сдвига и оказалась в начале.

Вставка i = 5, key = 3. j = 4: a[4] = 6 > 3, сдвигаем: a[5] = 6. j = 3: a[3] = 5 > 3, сдвигаем: a[4] = 5. j = 2: a[2] = 4 > 3, сдвигаем: a[3] = 4. j = 1: a[1] = 2 > 3? Нет. Кладём a[2] = 3. Массив [1, 2, 3, 4, 5, 6] — упорядочен.

Теперь код. Функция сортирует на месте, null отсекается.

using System;

int[] data = { 5, 2, 4, 6, 1, 3 };
InsertionSort(data);
Print(data);

int[] empty = Array.Empty<int>();
InsertionSort(empty);
Print(empty);

int[] one = { 9 };
InsertionSort(one);
Print(one);

int[] equal = { 4, 4, 4 };
InsertionSort(equal);
Print(equal);

int[] negative = { -2, 5, -2, 0, 7 };
InsertionSort(negative);
Print(negative);

void InsertionSort(int[] a)
{
    if (a == null) throw new ArgumentNullException(nameof(a));
    int n = a.Length;
    for (int i = 1; i < n; i++)
    {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

void Print(int[] a)
{
    if (a.Length == 0)
    {
        Console.WriteLine("(пусто)");
        return;
    }
    Console.WriteLine(string.Join(" ", a));
}

Вывод:

1 2 3 4 5 6
(пусто)
9
4 4 4
-2 -2 0 5 7

Разберём случаи. Основной массив [5, 2, 4, 6, 1, 3] отсортирован в [1, 2, 3, 4, 5, 6]. Пустой массив: внешний цикл начинается с i = 1, но n = 0, условие ложно, ничего не выполняется, печатается «(пусто)». Один элемент: то же самое, остаётся 9. Массив из равных четвёрок уже упорядочен, вставки не делают сдвигов. Отрицательные числа сортируются так же, как положительные; массив [−2, 5, −2, 0, 7] превращается в [−2, −2, 0, 5, 7].

Стоимость и роль инверсий

Посчитаем сравнения и сдвиги. На каждой итерации i мы движемся по префиксу справа налево, пока a[j] > key. В худшем случае — когда массив упорядочен по убыванию — на итерации i делается i сдвигов, и суммарно получается 1 + 2 + … + (n − 1) = n(n − 1)/2, то есть O(n²). В лучшем случае — когда массив уже упорядочен — на каждой итерации условие a[j] > key сразу ложно, сдвигов нет, и общая работа — n − 1 сравнений, то есть O(n). Память — O(1): только key, i и j.

Чтобы понять, от чего зависит число сдвигов, введём полезное понятие. Инверсия — это пара позиций i < j, таких что a[i] > a[j]. То есть два элемента стоят «не в том порядке»: левый больше правого, хотя должен был быть правее. В упорядоченном массиве инверсий нет. В обратном порядке — их n(n − 1)/2.

Как связаны инверсии и вставки? Каждый сдвиг в сортировке вставками устраняет ровно одну инверсию. Сдвигаем a[j] вправо, потому что он больше key; тем самым мы разбираемся с парой (j, i) — а она и была инверсией. Одно перемещение — одна исчезнувшая инверсия. На самом деле можно сказать точнее: общее число сдвигов за всю работу алгоритма равно числу инверсий в исходном массиве. Правда, есть тонкость: во время сдвигов в массиве временно присутствует дубликат сдвигаемого значения, а key сохранён отдельно, поэтому считать инверсии прямо в рабочем массиве на промежуточных шагах не совсем корректно — мы ведь ещё не вставили key. Но суммарный итог всё равно равен исходному числу инверсий, потому что каждая вставка устраняет ровно столько инверсий, сколько делает сдвигов.

Отсюда важный вывод: время сортировки вставками — O(n + I), где I — число инверсий в исходном массиве. Если инверсий мало, алгоритм работает близко к линейному. Если инверсий много, он вырождается в квадратичный.

Проверим это на массиве, который выглядел почти упорядоченным: [2, 3, 4, 5, 1]. Инверсий здесь ровно четыре: каждое из четырёх чисел 2, 3, 4, 5 образует инверсию с единицей. И сортировка вставками разберётся с ними за одну длинную вставку: key = 1, и он сдвигает 5, 4, 3, 2 вправо за четыре шага, после чего встаёт на первое место. Всего четыре сдвига, плюс несколько сравнений — линейно по n. Пузырьковая сортировка, как мы видели в прошлом уроке, на этом же массиве делала четыре прохода и оставалась квадратичной. Вот в чём разница: пузырёк двигает маленький элемент влево на одну позицию за проход, а вставка переносит его на нужное место сразу за один заход.

Здесь важно оговориться. Утверждение «сортировка вставками быстра на почти отсортированных данных» имеет точный смысл: она быстра, когда инверсий мало. Без этого определения фраза «почти отсортированный» размыта. Массив [2, 3, 4, 5, 1] действительно почти отсортирован в этом смысле — четыре инверсии. А массив [5, 4, 3, 2, 1] тоже выглядит «почти упорядоченным» на глаз, но инверсий в нём n(n − 1)/2, и вставками он будет сортироваться квадратично. Поэтому полезно мыслить не через внешнее впечатление, а через число инверсий.

Внутренний цикл использует строгое условие a[j] > key. Равные элементы не сдвигаются, и key вставляется после всех равных ему — то есть справа от них. Это значит, что относительный порядок элементов с одинаковыми ключами сохраняется: если в исходном массиве два равных элемента шли в определённом порядке, они в том же порядке и останутся. Сортировка вставками стабильна. Если бы мы использовали >=, то равный элемент сдвигался бы вправо, key вставлялся бы слева от него, и порядок равных менялся бы. Так же, как в пузырьковой, знак сравнения здесь не случаен.

Мы разобрали три сортировки: выбором, пузырьковую и вставками. Все три квадратичны в худшем случае, но каждая по-своему: выбор всегда делает одинаковое число сравнений, пузырёк умеет рано останавливаться, вставка выигрывает при малом числе инверсий. Существуют и более быстрые сортировки, но их разбор впереди. Сейчас нам важно было увидеть, как одна и та же задача — упорядочить массив — решается разными способами, и как эти способы отличаются по поведению на разных данных.