Изменения
Новая страница: «'''Сортировка вставками''' - квадратичный алгоритм сортировки. ==Алгоритм== На каждом шаге ал…»
'''Сортировка вставками''' - квадратичный алгоритм сортировки.
==Алгоритм==
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
В худшем случае, время работы массива составит <TeX>\theta(n^2)</TeX>
==Псевдокод==
'''Вход''': массив A, состоящий из элементов A[1], A[2], ..., A[n]
'''for''' i = 2, 3, ..., n: <!-- начинаем с i=2, это не ошибка. Можно и с i=1, но это просто будет лишняя итерация -->
key := A[i]
j := i - 1
'''while''' j > 0 '''and''' A[j] > key:
A[j + 1] := A[j]
j := j - 1
A[j + 1] := key
==Пример работы==
Пример работы алгоритма для массива [5, 2, 4, 3, 1]
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| До
!style="background-color:#EEE"| После
!style="background-color:#EEE"| Описание шага
|-
|''Первый проход(проталкиваем второй элемент '''''(2)''''')''
|-
|style="background-color:#FFF;padding:2px 10px"| '''5 2''' 4 3 1
|style="background-color:#FFF;padding:2px 10px"| '''2 5''' 4 3 1
|style="background-color:#FFF;padding:2px 10px"| Алгоритм сравнивает второй элемент с первым и меняет их местами.
|-
|''Второй проход(проталкиваем третий элемент '''''(4)''''')''
|-
|style="background-color:#FFF;padding:2px 10px"| 2 '''5 4''' 3 1
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 5''' 3 1
|style="background-color:#FFF;padding:2px 10px"| Сравнивает третий со вторым и меняет местами
|-
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется
|-
|''Третий проход(проталкиваем четвертый элемент '''''(3)''''')''
|-
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''5 3''' 1
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''3 5''' 1
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами
|-
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 3''' 5 1
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 4''' 5 1
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами
|-
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется
|-
|''Четвертый проход(проталкиваем пятый элемент '''''(1)''''')''
|-
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''5 1'''
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''1 5'''
|style="background-color:#FFF;padding:2px 10px"| Меняет пятый и четвертый местами
|-
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''4 1''' 5
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''1 4''' 5
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами
|-
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 1''' 4 5
|style="background-color:#FFF;padding:2px 10px"| 2 '''1 3''' 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами
|-
|style="background-color:#FFF;padding:2px 10px"| '''2 1''' 3 4 5
|style="background-color:#FFF;padding:2px 10px"| '''1 2''' 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняет второй и первый местами. Массив отсортирован.
|}
== См. также ==
* [[Сортировка пузырьком]]
* [[Сортировка выбором]]
* [[Сортировка кучей]]
* [[Сортировка слиянием]]
* [[Быстрая сортировка]]
* [[Сортировка подсчетом]]
==Алгоритм==
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
В худшем случае, время работы массива составит <TeX>\theta(n^2)</TeX>
==Псевдокод==
'''Вход''': массив A, состоящий из элементов A[1], A[2], ..., A[n]
'''for''' i = 2, 3, ..., n: <!-- начинаем с i=2, это не ошибка. Можно и с i=1, но это просто будет лишняя итерация -->
key := A[i]
j := i - 1
'''while''' j > 0 '''and''' A[j] > key:
A[j + 1] := A[j]
j := j - 1
A[j + 1] := key
==Пример работы==
Пример работы алгоритма для массива [5, 2, 4, 3, 1]
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| До
!style="background-color:#EEE"| После
!style="background-color:#EEE"| Описание шага
|-
|''Первый проход(проталкиваем второй элемент '''''(2)''''')''
|-
|style="background-color:#FFF;padding:2px 10px"| '''5 2''' 4 3 1
|style="background-color:#FFF;padding:2px 10px"| '''2 5''' 4 3 1
|style="background-color:#FFF;padding:2px 10px"| Алгоритм сравнивает второй элемент с первым и меняет их местами.
|-
|''Второй проход(проталкиваем третий элемент '''''(4)''''')''
|-
|style="background-color:#FFF;padding:2px 10px"| 2 '''5 4''' 3 1
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 5''' 3 1
|style="background-color:#FFF;padding:2px 10px"| Сравнивает третий со вторым и меняет местами
|-
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется
|-
|''Третий проход(проталкиваем четвертый элемент '''''(3)''''')''
|-
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''5 3''' 1
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''3 5''' 1
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами
|-
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 3''' 5 1
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 4''' 5 1
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами
|-
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется
|-
|''Четвертый проход(проталкиваем пятый элемент '''''(1)''''')''
|-
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''5 1'''
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''1 5'''
|style="background-color:#FFF;padding:2px 10px"| Меняет пятый и четвертый местами
|-
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''4 1''' 5
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''1 4''' 5
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами
|-
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 1''' 4 5
|style="background-color:#FFF;padding:2px 10px"| 2 '''1 3''' 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами
|-
|style="background-color:#FFF;padding:2px 10px"| '''2 1''' 3 4 5
|style="background-color:#FFF;padding:2px 10px"| '''1 2''' 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняет второй и первый местами. Массив отсортирован.
|}
== См. также ==
* [[Сортировка пузырьком]]
* [[Сортировка выбором]]
* [[Сортировка кучей]]
* [[Сортировка слиянием]]
* [[Быстрая сортировка]]
* [[Сортировка подсчетом]]
