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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

Ссылки

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

Сортировка вставками в Википедии
Insertion sort on Wikipedia
Реализация на различных ЯП

Добавить комментарий