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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
(Псевдокод)
Строка 7: Строка 7:
  
 
==Псевдокод==
 
==Псевдокод==
'''Вход''': массив A, состоящий из элементов A[1], A[2], ..., A[n]
+
<wikitex>
   
+
  for (int i = 1; i $\leqslant$ n-1; i++)
'''for''' i = 2, 3, ..., n:  <!-- начинаем с i=2, это не ошибка. Можно и с i=1, но это просто будет лишняя итерация -->
+
     j $\leftarrow$ i - 1
    key := A[i]
+
     while (j $\geqslant$ 0 && a[j] > a[j+1])
     j := i - 1
+
         a[j] $\leftrightarrow$ a[j+1]
     '''while''' j > 0 '''and''' A[j] > key:
+
         j $\leftarrow$ j-1
         A[j + 1] := A[j]
+
</wikitex>
         j := j - 1
 
    A[j + 1] := key
 
  
 
==Пример работы==
 
==Пример работы==

Версия 21:20, 4 мая 2012

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

Алгоритм

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

В худшем случае, время работы массива составит $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 Меняет второй и первый местами. Массив отсортирован.

См. также


Источники

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