Изменения

Перейти к: навигация, поиск

Сортировка вставками

5 байт убрано, 9 февраль
исправлена опечатка "на на" -> "на"
== Оптимизации ==
=== Бинарные вставки ===
Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.
'''function''' insertionSort(a):
'''for''' i = 1 '''to''' n - 1
Анонимный участник

Навигация