Изменения

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

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

1460 байт добавлено, 00:54, 4 июня 2014
Нет описания правки
<wikitex>Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве $<tex>\displaystyle \frac {n(n - 1)} {2}$</tex>.
Алгоритм работает за $O(n + k)$, где k — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за $O(n^2)$. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.
==Псевдокод==
'''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])
j = j - 1
==Пример работы==
Пример работы алгоритма для массива [<tex>5, 2, 4, 3, 1]</tex>
{| style="background-color:#CCC;margin:0.5px"
== Оптимизации ==
=== Бинарные вставки ===
Так как в среднем количество сравнений для <tex>j</tex>-го элемента равно <tex>j/2</tex>, следовательно общее количество сравнений приблизительно <tex>\displaystyle \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} log N</tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить <tex>R_j</tex> элемент на <tex>i</tex>-тое место, всё ещё необходимо переместить <tex>j-i</tex> элементов. В итоге время выполнения алгоритма уменьшилось в среднем в четыре раза : <tex>O(C \cdot N \cdot (N/48+log_{2} \log N) \approx ) = O(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])
=== Двухпутевые вставки ===
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём сдвига элементов влево или вправо туда, куда выгоднее.
Пример для набора элементов <tex>5 , 7 , 3 , 4 , 6 </tex> {| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| До!style="background-color:#EEE"| После!style="background-color:#EEE"| Описание шага|-|colspan=3|''Первый проход (проталкиваем второй элемент — '''''5''''')''|-|style="background-color:#FFF;padding:2px 10px"| |style="background-color:#FFF;padding:2px 10px"| '''5'''|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов то мы просто добавляем элемент туда.|-|colspan=3|''Второй проход (проталкиваем третий элемент — '''''7''''')'' |-|style="background-color:#FFF;padding:2px 10px"| 5 |style="background-color:#FFF;padding:2px 10px"| 5 '''7'''|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.|- |colspan=3|''Третий проход (проталкиваем четвертый — '''''3''''')''|-|style="background-color:#FFF;padding:2px 10px"| 5 7|style="background-color:#FFF;padding:2px 10px"| '''3''' 5 7|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.|-|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''4''''')''|-|style="background-color:#FFF;padding:2px 10px"| 3 5 7 |style="background-color:#FFF;padding:2px 10px"| 3 '''4''' 5 7 |style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше ем до правого то сдвигаем левую часть.|-|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''6''''')''|-|style="background-color:#FFF;padding:2px 10px"| 3 4 5 7 |style="background-color:#FFF;padding:2px 10px"| 3 4 5 '''6 ''' 7 |style="background-color:#FFF;padding:2px 10px"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.|} Как можно заметить структура поля вывода имеет сходство с Двусвязной очередью, а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в восемь раз , благодаря тому что теперь мы вместо перемещения в среднем <tex>N/2</tex> мы перемещаем <tex>N/4</tex> элементов : <tex>O(C \cdot N \cdot (N/8+log_{2} \log N) \approx ) = O(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>O(C \cdot N \cdot (N/4+2) \approx ) = O( N^2/4)</tex>, следовательно <tex>C=1/4</tex>.
=== Сортировка с вычислением адреса ===
Сортировку с вычисление адреса выгодно использовать когда ключи распределены равномерно и не скапливаются хаотично в отдельных диапазонах значений. Вместо левой отсортированной части массива мы будем использовать <tex> M </tex> односвязных списков, в каждом из которых будут храниться значения из определённого диапазона. С каждым списком работаем как при простых выставках в список. Вероятность того что элемент попадёт в какой-либо список <tex>1/M</tex>, следовательно для каждого элемента происходит примерно <tex> \displaystyle \frac {N} {4 \cdot M} </tex> сравнений, следовательно общее количество сравнений <tex> \displaystyle \frac {N^2} {4 \cdot M} </tex>, а при <tex>M</tex> порядка <tex>N</tex> асимптотическая сложность уменьшается до <tex>O(N)</tex>.
Рассмотрим на примере.
Входные данные : <tex>867 , 345 , 984 , 245 , 123 , 743 , 550 , 490 , 300 </tex> Будем использовать 4 списка с соответствующими диапазонами значений : <tex>0 - 250, 251 - 500, 501 - 750, 751- 1000</tex>.
{|border="1"
|
* [[Быстрая сортировка]]
* [[Сортировка подсчетом]]
* [[Сортировка Шелла]]
== Источники ==
* [http://ru.wikipedia.org/wiki/Сортировка_вставками Сортировка вставками — Википедия]
Анонимный участник

Навигация