Сортировка вставками - это алгоритм сортировки, который имитирует человеческую сортировку вещей.
История возникновения сортировки вставками
Данный алгоритм существует с очень давних времен, так как он интуитивно понятен и прост. Первое упоминание данного метода происходит в 1928 году в книге Джона фон Неймана "Введение в математический анализ".
Сложность сортировки вставками
Сложность алгоритма сортировки вставками имеет несколько вариаций:
- Если массив отсортирован. Сложность сравнений будет равняться O(n) и количество замен = 0.
- Если массив частично отсортирован. Сложность сравнений будет равняться O(n^2) и O(n^2/4) замен.
- Если массив полностью не отсортирован. Сложность сравнений и замен будет равняться O(n^2).
Как видно, сортировка вставками куда более гибок по сложности, чем алгоритм сортировки пузырьком.
Алгоритм сортировки вставками
Для начала необходимо загрузить массив элементов А, после узнать его длину n. Если n<=1, то сортировка не свершится, в противном случае начинается процесс сортировки вставками. Создаем цикл, в котором начинаем работу со второго элемента массива, в цикле запоминаем текущий элемент и находим позицию для вставки текущего элемента, после сдвигаем элементы, которые больше текущего, вправо и вставляем текущий элемент на найденную позицию. После выводим массив А на печать.
Ручной пример работы сортировки вставками
На рисунке выше представлен ручной просчет сортировки вставками. Было произведено 12 шагов, чтобы полностью отсортировать массив из 12 элементов.
Достоинства и недостатки сортировки вставками
Алгоритм сортировки вставками имеет следующие достоинства:
- Не меняет относительный порядок равных элементов.
- Эффективный алгоритм для небольших или частично отсортированных данных.
- Не требует дополнительной памяти.
Алгоритм сортировки вставками имеет следующие недостатки:
- Неэффективен для больших или обратно отсортированных данных.
- Его время выполнения растет пропорционально квадрату размера входных данных.
- Неустойчив к ошибкам округления.