77
правок
Изменения
Нет описания правки
'''void''' insertionSort(a):
'''for''' i = 1 '''to''' n - 1
j= i --1
'''while''' j <tex> \geqslant </tex> 0 '''and''' a[j] > a[j + 1]
swap(a[j], a[j + 1])
==Пример работы==
== Оптимизации ==
=== Бинарные вставки ===
Теперь вместо линейного поиска позиции мы будем использовать [http://ru.wikipedia.org/wiki/Двоичный_поиск Бинарный [Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось . Бинарные вставки выгодно использовать только в среднем в два раза : <tex>N \cdot (N/4 + \log N) = N^2/4</tex>случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.
'''void''' insertionSort(a) :
'''for''' i = 1 '''to''' n - 1
j= i --1
k = '''BinSearch'''(a, a[i], 0, j)
'''for ''' m = j '''downto''' k swap(a[jm], a[jm+1])
=== Двухпутевые вставки ===
|style="background-color:#FFF;padding:2px 10px"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.
|}
Как можно заметить структура поля вывода имеет сходство с [http[wikipedia://ru.wikipedia.org/wiki/Двусвязная_очередь Двусвязной :Двусвязная очередь | двусвязной очередью]], а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в четыре раза, благодаря тому что теперь мы вместо перемещения в среднем <tex>N/2</tex> мы перемещаем <tex>N/4</tex> элементов : <tex>N \cdot (N/8+\log N) = N^2/8</tex>.
* [[Сортировка Шелла]]
== Источники ==
* [http[wikipedia://ru.wikipedia.org/wiki/Сортировка_вставками :Сортировка вставками|Сортировка вставками — {{---}} Википедия]]
* Н. Вирт «Алгоритмы и структуры данных», часть 2.2.1 "Сортировка с помощью прямого включения"
== Дополнительные материалы ==
