Изменения
Нет описания правки
|style="background-color:#FFF;padding:2px 10px"| Меняет второй и первый местами. Массив отсортирован.
|}
== Оптимизации ==
=== Бинарные вставки ===
Так как в среднем количество сравнений для <tex>j</tex>-го элемента равно <tex>j/2</tex>, следовательно общее количество сравнений приблизительно <tex>\frac {(1+2+3+...+N)}{2} \approx N^2/4</tex>, но это очень много даже при малых <tex>N</tex>. Суть этого заключается в том, что поиск позиции для вставки <tex>j</tex>-го элемента осуществляется бинарным поиском, вследствие чего количество сравнений для <tex>N</tex> элементов <tex>N \cdot \log_{2} N</tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить <tex>R_j</tex> элемент на <tex>i</tex>-тое место, всё ещё необходимо переместить <tex>j-i</tex> элементов. В итоге время выполнения алгоритма уменьшилось в среднем в четыре раза : <tex>C \cdot N \cdot (N/4+log_{2} N) \approx N^2/4</tex>, следовательно <tex>C=1/4</tex>.
InsertionSort(a)
for i = 1 to n - 1:
j = i - 1
k = BinSearch(a, a[i], 0, j)
swap(a[k], a[i])
=== Двухпутевые вставки ===
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём сдвига элементов влево или вправо туда, куда выгоднее.
Пример для набора элементов 5 7 3 4 6
5
5 7
3 5 7
3 4 5 7
3 4 5 6 7
Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в восемь раз : <tex>C \cdot N \cdot (N/8+log_{2} N) \approx N^2/8</tex>, следовательно <tex>C=1/8</tex>.
=== Метод Шелла ===
Метод Шелла основан на том, что сортировка вставками более эффективна на маленьких или на частичной отсортированных входных данных. Устройство метода Шелла более понятно если рассматривать его на фиксированном наборе данных. Например мы имеем набор из 16 элементов <tex>R_1...R_{16}</tex> разобьём их на пары <tex>(R_1,R_9),...,(R_8,R_{16})</tex>. Каждое разделение называется проходом. Отсортируем каждую из пар. Разобьем на группы по 4 элемента <tex>(R_1,R_5,R_9,R_{13}),...,(R_4,R_8,R_{12},R_{16})</tex>. Отсортируем каждую из пар. Разобьём на 2 группы по восемь элементов <tex>(R_1,R_3,R_5,R_7,R_9,R_{11},R_{13},R_{15}),(R_2,R_4,R_6,R_8,R_{10},R_{12},R_{14},R_{16})</tex>. Отсортируем каждую из пар. При четвёртоми последнем проходе сортируются все 16 элементов. В итоге получится отсортированный массив.
Последовательность смещений 1 2 4 8 может меняться в зависимости от неё меняется и асимптотика. Например предложенная Хиббардом последовательность <tex>2^i-1 \le N, i \in N </tex> приводит к алгоритму с асимптотиткой <tex> O(N^{3/2}) </tex>.
===Вставка в список ===
При этой сортировке мы используем односвязной список вместо упорядоченной части массива. Теперь на не потребуется времени на сдвиг, а понадобиться всего лишь изменить родственные связи. При этом время выполнения сокращается в четыре раза : <tex>C \cdot N \cdot (N/4+2) \approx N^2/4</tex>, следовательно <tex>C=1/4</tex>.
=== Сортировка с вычислением адреса ===
Сортировку с вычисление адреса выгодно использовать когда ключи распределены равномерно и не скапливаются хаотично в отдельных диапазонах значений. Вместо левой отсортированной части массива мы будем использовать <tex> M </tex> односвязных списков, в каждом из которых будут храниться значения из определённого диапазона. С каждым списком работаем как при простых выставках в список. Вероятность того что элемент попадёт в какой-либо список <tex>1/M</tex>, следовательно для каждого элемента происходит примерно <tex> \frac {N} {4 \cdot M} </tex> сравнений, следовательно общее количество сравнений <tex> \frac {N^2} {4 \cdot M} </tex>, а при <tex>M</tex> порядка <tex>N</tex> асимптотическая сложность уменьшается до <tex>O(N)</tex>.
Рассмотрим на примере.
Входные данные : 867 345 984 245 123 743 550 490 300
Будем использовать 4 списка с соответствующими диапазонами значений : 0 - 250, 251 - 500, 501 - 750, 751- 1000.
{|border="1"
|
|3 элемента
|6 элементов
|9 элементов
|-
|0 - 250
|
|123 245
|123 245
|-
|251 - 500
|345
|345
|300 345 490
|-
|501 - 750
|
|743
|550 743
|-
|751 - 1000
|867 984
|867 984
|867 984
|}
== Сложность ==
Так как алгоритм сравнивает и меняет местами соседние элементы пока не найдёт подходящую позицию, то худший случай будет при входных данных отсортированных в обратном порядке.
== См. также ==
* [[Сортировка пузырьком]]
* [[Сортировка подсчетом]]
== Источники ==
* [http://ru.wikipedia.org/wiki/Сортировка_вставками Сортировка вставками — Википедия - свободная энциклопедия]
* Н. Вирт «Алгоритмы и структуры данных», часть 2.2.1 "Сортировка с помощью прямого включения"
== Дополнительные материалы ==
