Сортировка простыми вставками :: Insertion sort
Одна из базовых сортировок. В общем случае работает достаточно медленно, однако очень эффективно сортирует почти упорядоченные массивы.
Сортировку вставками можно получить, если немного видоизменить гномью сортировку.
Алгоритм
В сортировке вставками последовательно обрабатываются отрезки массива, начиная с первого элемента и затем последовательно расширяя подмассив, вставляя на своё место очередной неотсортированный элемент.
Для вставки используется буферная область памяти, в которой хранится элемент, ещё не вставленный на своё место (так называемый ключевой элемент). В подмассиве, начиная с конца отрезка, перебираются элементы, которые сравниваются с ключевым. Если эти элементы больше ключевого, то они сдивгаются на одну позицию вправо, освобождая место для последующих элементов. Если в результате этого перебора попадается элемент, меньший или равный ключевому, то значит в текущую свободную ячейку можно вставить ключевой элемент.
Наилучший случай
Наиболее хорошо данная сортировка себя показывает применительно к почти отсортированным массивами. В этом случае алгоритм показывает наилучшую временную сложность по сравнению с различными "эффективными" сортировками, вроде быстрой сортировки или сортировки слиянием.
Наихудший случай
Таковым является реверсно упорядоченный массив. Улучшенный вариант сортировки вставками - сортировка Шелла, обходит данную проблему.
Характеристики алгоритма
| Название | Сортировка простыми вставками (Insertion sort) | |
|---|---|---|
| Класс | Сортировки вставками | |
| Устойчивость | Да | |
| Сравнения | Да | |
| Сложность по времени | Худшая | O(n2 / 2) |
| Средняя | O(n2 / 4) | |
| Лучшая | O(n) | |
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Сортировка вставками
Реализация на различных ЯП