1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''Сортировка вставками''' (англ. ''Insertion sort'') — квадратичный алгоритм [[Сортировка|сортировки]].
==Алгоритм==
== Оптимизации ==
=== Бинарные вставки ===
Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.
'''function''' insertionSort(a):
'''for''' i = 1 '''to''' n - 1
!style="background-color:#EEE"| Описание шага
|-
|colspan=3|''Первый проход (проталкиваем второй первый элемент — '''''5''''')''
|-
|style="background-color:#FFF;padding:2px 10px"|
|style="background-color:#FFF;padding:2px 30px"| '''5'''
|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов , то мы просто добавляем элемент туда.
|-
|colspan=3|''Второй проход (проталкиваем третий второй элемент — '''''7''''')''
|-
|style="background-color:#FFF;padding:2px 30px"| 5
|style="background-color:#FFF;padding:2px 30px"| 5 '''7'''
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и , так как позиция крайняя , то сдвигать ничего не приходится.
|-
|colspan=3|''Третий проход (проталкиваем четвертый третий — '''''3''''')''
|-
|style="background-color:#FFF;padding:2px 30px"| 5 7
|style="background-color:#FFF;padding:2px 20px"| '''3''' 5 7
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и , так как позиция крайняя , то сдвигать ничего не приходится.
|-
|colspan=3|''Четвертый проход (проталкиваем пятый четвертый элемент — '''''4''''')''
|-
|style="background-color:#FFF;padding:2px 20px"| 3 5 7
|style="background-color:#FFF;padding:2px 10px"| 3 '''4''' 5 7
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше ем , чем до правого то , значит сдвигаем левую часть.
|-
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''6''''')''
