Изменения
Нет описания правки
==Алгоритм==
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве <tex>\displaystyle \frac {n(n - 1)} {2}</tex>.
Алгоритм работает за $<tex>O(n + k)$</tex>, где k — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за $<tex>O(n^2)$</tex>. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.</wikitex>
==Псевдокод==
'''InsertionSortvoid'''insertionSort(a): '''for''' i = 1 '''to ''' n - 1: j = i - 1- '''while''' (j <tex> \geqslant </tex> 0) '''and ''' (a[j] > a[j + 1]): '''swap'''(a[j], a[j + 1])
j = j - 1
=== Бинарные вставки ===
Так как в среднем количество сравнений для <tex>j</tex>-го элемента равно <tex>j/2</tex>, следовательно общее количество сравнений приблизительно <tex>\displaystyle \frac {(1+2+3+...+N)}{2} = N^2/4</tex>, но это очень много даже при малых <tex>N</tex>. Суть этого заключается в том, что поиск позиции для вставки <tex>j</tex>-го элемента осуществляется бинарным поиском, вследствие чего количество сравнений для <tex>N</tex> элементов <tex> N\log N </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить <tex>R_j</tex> элемент на <tex>i</tex>-тое место, всё ещё необходимо переместить <tex>j-i</tex> элементов. В итоге время выполнения алгоритма уменьшилось в среднем в два раза : <tex>O(C \cdot N \cdot (N/4 + \log N)) = O(N^2/4)</tex>, следовательно <tex>C=1/4</tex>.
'''InsertionSort'void'''insertionSort(a): '''for''' i = 1 '''to ''' n - 1: j = i - 1- k = '''BinSearch'''(a, a[i], 0, j) '''swap'''(a[k], a[i])
=== Двухпутевые вставки ===
