Изменения
Нет описания правки
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве <tex>\displaystyle \frac {n(n - 1)} {2}</tex>.
Алгоритм работает за <tex>O(n + k)</tex>, где <tex>k </tex> — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за <tex>O(n^2)</tex>. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.
==Псевдокод==
'''for''' i = 1 '''to''' n - 1
j--
'''while''' j <tex> \geqslant </tex> 0) '''and''' (a[j] > a[j + 1]
swap(a[j], a[j + 1])
j = j - 1
==Пример работы==
Пример работы алгоритма для массива <tex>[ 5, 2, 4, 3, 1]</tex>
{| style="background-color:#CCC;margin:0.5px"
== Оптимизации ==
=== Бинарные вставки ===
'''void''' insertionSort(a) :
'''for''' i = 1 '''to''' n - 1
=== Двухпутевые вставки ===
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём путём сдвига элементов влево или вправо туда, куда выгоднее.Пример для набора элементов <tex>[ 5, 7, 3, 4, 6]</tex>
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| До
|-
|style="background-color:#FFF;padding:2px 10px"|
|style="background-color:#FFF;padding:2px 10px30px"| '''5'''
|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов то мы просто добавляем элемент туда.
|-
|colspan=3|''Второй проход (проталкиваем третий элемент — '''''7''''')''
|-
|style="background-color:#FFF;padding:2px 10px30px"| 5 |style="background-color:#FFF;padding:2px 10px30px"| 5 '''7'''
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.
|-
|colspan=3|''Третий проход (проталкиваем четвертый — '''''3''''')''
|-
|style="background-color:#FFF;padding:2px 10px30px"| 5 7|style="background-color:#FFF;padding:2px 10px20px"| '''3''' 5 7
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.
|-
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''4''''')''
|-
|style="background-color:#FFF;padding:2px 10px20px"| 3 5 7
|style="background-color:#FFF;padding:2px 10px"| 3 '''4''' 5 7
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше ем до правого то сдвигаем левую часть.
|style="background-color:#FFF;padding:2px 10px"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.
|}
Как можно заметить структура поля вывода имеет сходство с [http://ru.wikipedia.org/wiki/Двусвязная_очередь Двусвязной очередью], а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в четыре раза, благодаря тому что теперь мы вместо перемещения в среднем <tex>N/2</tex> мы перемещаем <tex>N/4</tex> элементов : <tex>O(C \cdot N \cdot (N/8+\log N)) = O(N^2/8)</tex>, следовательно <tex>C=1/8</tex>.
