Сортировка простыми вставками :: Insertion sort

Одна из базовых сортировок. В общем случае работает достаточно медленно, однако очень эффективно сортирует почти упорядоченные массивы.

Сортировку вставками можно получить, если немного видоизменить гномью сортировку.

Алгоритм

В сортировке вставками последовательно обрабатываются отрезки массива, начиная с первого элемента и затем последовательно расширяя подмассив, вставляя на своё место очередной неотсортированный элемент.

Для вставки используется буферная область памяти, в которой хранится элемент, ещё не вставленный на своё место (так называемый ключевой элемент). В подмассиве, начиная с конца отрезка, перебираются элементы, которые сравниваются с ключевым. Если эти элементы больше ключевого, то они сдивгаются на одну позицию вправо, освобождая место для последующих элементов. Если в результате этого перебора попадается элемент, меньший или равный ключевому, то значит в текущую свободную ячейку можно вставить ключевой элемент.

Наилучший случай

Наиболее хорошо данная сортировка себя показывает применительно к почти отсортированным массивами. В этом случае алгоритм показывает наилучшую временную сложность по сравнению с различными "эффективными" сортировками, вроде быстрой сортировки или сортировки слиянием.

Наихудший случай

Таковым является реверсно упорядоченный массив. Улучшенный вариант сортировки вставками - сортировка Шелла, обходит данную проблему.

Характеристики алгоритма

НазваниеСортировка простыми вставками (Insertion sort)
КлассСортировки вставками
УстойчивостьДа
СравненияДа
Сложность по времениХудшаяO(n2 / 2)
СредняяO(n2 / 4)
ЛучшаяO(n)
Сложность по памятиОбщаяO(n)
ДополнительнаяO(1)

Ссылки

Сортировки вставками

Глупая сортировка и некоторые другие, поумнее

Сортировка вставками

Insertion sort

Реализация на различных ЯП