Сортировка вставками — один из алгоритмов сортировки. Для сортировки элементов массива по возрастанию или по убыванию можно использовать сортировку вставками.

Принцип сортировки вставками

Массив разделен на две части (не на самом деле), левая часть отсортирована, а правая часть не отсортирована. Итерируя слева направо и перемещая нашу линию, которая разделяется вправо, мы делаем весь массив отсортированным.

Этапы алгоритма

  1. Перебирать массив от индекса 1 до n-1, т.е. перебирать весь массив, поскольку 0-й элемент уже отсортирован. (0 базовая индексация)
  2. На каждой итерации проверяйте, больше ли текущий элемент, чем предыдущий. Если это так, то текущий элемент находится в правильной позиции, и мы продолжаем.
  3. А если нет, то мы должны поместить его в правильное положение, сравнив все элементы позади и переместив их на 1 шаг вперед, пока не найдем правильное положение для этого текущего элемента.
  4. К концу всех итераций мы получаем отсортированный весь массив.

Пример

  1. Возьмите пример arr [6, 2, 3, 5, 9, 8, 1] из n = 7 элементов. Первый шаг - перебрать arr с индекса 1.
  2. Таким образом, при индексе i=1 проверьте [6,2], поэтому 2 не находится в правильном положении, т.е. сравните 2 с предыдущими элементами и переместите их вправо, пока мы не найдем меньший элемент, чем 2. поэтому здесь 6 будет перемещен в индекс 1 а затем присвойте 2 его правильной позиции, так что теперь массив до индекса 1 отсортирован. [2, 6]
  3. Аналогично шагу 2 для каждого я делаю то же самое, и, наконец, весь массив будет отсортирован. Смотрите изображение ниже для лучшего понимания.

Реализация сортировки вставками в C++

Важные факты о сортировке вставками

Временная сложность: O(n²), пространственная сложность: O(1)

Лучший случай: когда массив уже отсортирован. Ом (н)

Худший случай: когда массив отсортирован в обратном порядке. О (n²)

Сортировка вставками — это сортировка на месте, что означает, что не требуется дополнительное пространство, как при сортировке слиянием.

Сортировка вставками является стабильной сортировкой, то есть если два элемента одинаковы, то эти элементы сохраняют свой порядок (порядок до сортировки) даже после сортировки.

Расширение сортировки вставками — сортировка Шелла.