Сортировка вставками
Сортировка вставками — это алгоритм, который последовательно строит упорядоченную часть массива: очередной элемент берётся из неупорядоченной части и вставляется в подходящее место.
Как работает алгоритм
Первый элемент считают упорядоченной частью из одного элемента. Затем рассматривают второй элемент, сравнивают его с элементами слева и сдвигают большие элементы на одну позицию вправо. Освободившееся место занимает рассматриваемый элемент. Такие действия повторяют для третьего, четвёртого и всех следующих элементов.
- Выбрать очередной элемент массива.
- Сохранить его значение во временной переменной.
- Сдвигать вправо элементы упорядоченной части, которые больше выбранного.
- Вставить выбранное значение в освободившуюся позицию.
В лучшем случае, когда массив уже упорядочен, алгоритм выполняет \(O(n)\) сравнений и почти не делает сдвигов. Дополнительная память обычно равна \(O(1)\), потому что элементы переставляются внутри исходного массива.
Массив \([4, 2, 5, 1]\). После обработки 2 получаем \([2, 4, 5, 1]\). Элемент 5 уже стоит после меньших элементов, поэтому порядок не меняется. При обработке 1 элементы 5, 4 и 2 сдвигаются вправо, результат: \([1, 2, 4, 5]\).
При сортировке вставками очередной элемент вставляется в готовую упорядоченную часть. В сортировке выбором на каждом шаге сначала ищут минимальный элемент в неупорядоченной части, а затем меняют его местами с первым элементом этой части.
Какой массив является упорядоченной частью после первого шага обработки массива \([7, 3, 5]\)?
Главное
- Сортировка вставками поддерживает левую часть массива в упорядоченном виде и вставляет в неё очередной элемент.
- Большие элементы передвигаются вправо, чтобы освободить место для вставляемого значения.
- Сложность обычно \(O(n^2)\), но для уже упорядоченного массива возможна линейная работа \(O(n)\).