Изменения

Перейти к: навигация, поиск

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

1083 байта убрано, 22:17, 20 мая 2012
Нет описания правки
<wikitex>На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
Алгоритм работает за $O(n + k)$, где k — число обменов элементов входного массива. В среднем и в худшем случае — за $O(n^2)$. Более точные Минимальные оценки работы алгоритма приведены нижевстречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.
</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$
|width=5%|&nbsp;
!style="background-color:#FFF"| $M_{best} = 3(n-1)$
|-
!style="background-color:#FFF"| $C_{average} = (n^2+n-2)/4$
|
!style="background-color:#FFF"| $M_{average} = (n^2+9n-10)/4$
|-
!style="background-color:#FFF"| $C_{worst} = (n^2+n-4)/4$
|
!style="background-color:#FFF"| $M_{worst} = (n^2+3n-4)/2$
|}
Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.</wikitex>
==Пример работы==
Пример работы алгоритма для массива [5, 2, 4, 3, 1]
Borisov
285
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/22584»

Навигация