Изменения

Алгоритм работает за $O(n + k)$, где k — число обменов элементов входного массива. В среднем и в худшем случае — за $O(n^2)$. Более точные оценки работы алгоритма приведены ниже.

</wikitex>

==Псевдокод==

<wikitex>

j $\leftarrow$ j - 1

</wikitex>

== Анализ алгоритма ==

<wikitex>Число сравнений ключей на i-ом просеивании ключей ($C_i$) самое большее равно $i-1$, самое меньшее — 1; если предположить, что все перестановки из $n$ ключей равновероятны, то среднее число сравнений $i/2$. Число же обменов элементов $M_i$ равно равно $C_i+2$. Поэтому общее число сравнений и число обменов таковы:

{| border="0"

!style="background-color:#FFF"| $C_{best} = n-1$

|}

Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.</wikitex>

==Пример работы==

Пример работы алгоритма для массива [5, 2, 4, 3, 1]

|style="background-color:#FFF;padding:2px 10px"| Меняет второй и первый местами. Массив отсортирован.

|}

== См. также ==

* [[Сортировка пузырьком]]

* [[Быстрая сортировка]]

* [[Сортировка подсчетом]]

== Источники ==

* [http://ru.wikipedia.org/wiki/Сортировка_вставками Википедия - свободная энциклопедия]

* Н. Вирт «Алгоритмы и структуры данных», часть 2.2.1 "Сортировка с помощью прямого включения"

== Дополнительные материалы ==

* [http://rain.ifmo.ru/cat/view.php/vis/sorts/quadratic-2010 Визуализатор квадратичных алгоритмов]