Сортировка вставками — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
<wikitex>На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
 
<wikitex>На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
  
−
Алгоритм работает за $O(n + k)$, где k — число обменов элементов входного массива. В среднем и в худшем случае — за $O(n^2)$. Более точные оценки работы алгоритма приведены ниже.
+
Алгоритм работает за $O(n + k)$, где k — число обменов элементов входного массива. В среднем и в худшем случае — за $O(n^2)$. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.
 
</wikitex>
 
</wikitex>
 
==Псевдокод==
 
==Псевдокод==
Строка 14: Строка 14:
 
         j $\leftarrow$ j - 1
 
         j $\leftarrow$ j - 1
 
</wikitex>
 
</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]
 
Пример работы алгоритма для массива [5, 2, 4, 3, 1]

Версия 22:17, 20 мая 2012

Сортировка вставками — квадратичный алгоритм сортировки.

Алгоритм

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

Алгоритм работает за $O(n + k)$, где k — число обменов элементов входного массива. В среднем и в худшем случае — за $O(n^2)$. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке. </wikitex>

Псевдокод

<wikitex> 

for (int i = 1; i $\leqslant$ n - 1; i++)
    j $\leftarrow$ i - 1
    while (j $\geqslant$ 0 && a[j] > a[j + 1])
        a[j] $\leftrightarrow$ a[j + 1]
        j $\leftarrow$ j - 1

</wikitex>

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

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

До После Описание шага
Первый проход (проталкиваем второй элемент — 2)
5 2 4 3 1 2 5 4 3 1 Алгоритм сравнивает второй элемент с первым и меняет их местами.
Второй проход (проталкиваем третий элемент — 4)
2 5 4 3 1 2 4 5 3 1 Сравнивает третий со вторым и меняет местами
2 4 5 3 1 2 4 5 3 1 Второй и первый отсортированы, swap не требуется
Третий проход (проталкиваем четвертый — 3)
2 4 5 3 1 2 4 3 5 1 Меняет четвертый и третий местами
2 4 3 5 1 2 3 4 5 1 Меняет третий и второй местами
2 3 4 5 1 2 3 4 5 1 Второй и первый отсортированы, swap не требуется
Четвертый проход (проталкиваем пятый элемент — 1)
2 3 4 5 1 2 3 4 1 5 Меняет пятый и четвертый местами
2 3 4 1 5 2 3 1 4 5 Меняет четвертый и третий местами
2 3 1 4 5 2 1 3 4 5 Меняет третий и второй местами
2 1 3 4 5 1 2 3 4 5 Меняет второй и первый местами. Массив отсортирован.

См. также

Источники

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Сортировка_вставками&oldid=22584»