Изменения

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

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

4 байта убрано, 16:46, 6 июня 2014
Бинарные вставки
=== Бинарные вставки ===
Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.
'''voidfunction''' insertionSort(a) :
'''for''' i = 1 '''to''' n - 1
j = i - 1
'''for''' m = j '''downto''' k
swap(a[m], a[m+1])
=== Двухпутевые вставки ===
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается путём сдвига элементов влево или вправо туда, куда выгоднее.

Навигация