Изменения

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

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

386 байт убрано, 04:20, 4 июня 2014
Нет описания правки
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве <tex>\displaystyle \frac {n(n - 1)} {2}</tex>.
Алгоритм работает за <tex>O(n + k)</tex>, где <tex>k </tex> — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за <tex>O(n^2)</tex>. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.
==Псевдокод==
'''for''' i = 1 '''to''' n - 1
j--
'''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<Теперь вместо линейного поиска позиции мы будем использовать [http://tex>-го элемента равно <tex>jru.wikipedia.org/2<wiki/tex>Двоичный_поиск Бинарный поиск], следовательно общее количество сравнений приблизительно изменится с <tex>\displaystyle \frac {O(1+2+3+...+N)}{2} = N^2/4)</tex>, но это очень много даже при малых <tex>N</tex>. Суть этого заключается в том, что поиск позиции для вставки <tex>j</tex>-го элемента осуществляется бинарным поиском, вследствие чего количество сравнений для <tex>N</tex> элементов до <tex> O(N\log N ) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить <tex>R_j</tex> элемент на <tex>i</tex>-тое на своё место, всё ещё необходимо переместить <tex>j-i</tex> большое количество элементов. В итоге время выполнения алгоритма уменьшилось в среднем в два раза : <tex>O(C \cdot N \cdot (N/4 + \log N)) = O(N^2/4)</tex>, следовательно <tex>C=1/4</tex>.
'''void''' insertionSort(a) :
'''for''' i = 1 '''to''' n - 1
j-- k = '''BinSearch'''(a, a[i], 0, j) for m = j '''downto''' k swap(a[kj], a[ij+1])
=== Двухпутевые вставки ===
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём путём сдвига элементов влево или вправо туда, куда выгоднее.Пример для набора элементов <tex>[ 5, 7, 3, 4, 6]</tex>
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| До
|-
|style="background-color:#FFF;padding:2px 10px"|
|style="background-color:#FFF;padding:2px 10px30px"| '''5'''
|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов то мы просто добавляем элемент туда.
|-
|colspan=3|''Второй проход (проталкиваем третий элемент — '''''7''''')''
|-
|style="background-color:#FFF;padding:2px 10px30px"| 5 |style="background-color:#FFF;padding:2px 10px30px"| 5 '''7'''
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.
|-
|colspan=3|''Третий проход (проталкиваем четвертый — '''''3''''')''
|-
|style="background-color:#FFF;padding:2px 10px30px"| 5 7|style="background-color:#FFF;padding:2px 10px20px"| '''3''' 5 7
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.
|-
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''4''''')''
|-
|style="background-color:#FFF;padding:2px 10px20px"| 3 5 7
|style="background-color:#FFF;padding:2px 10px"| 3 '''4''' 5 7
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше ем до правого то сдвигаем левую часть.
|style="background-color:#FFF;padding:2px 10px"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.
|}
Как можно заметить структура поля вывода имеет сходство с [http://ru.wikipedia.org/wiki/Двусвязная_очередь Двусвязной очередью], а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в четыре раза, благодаря тому что теперь мы вместо перемещения в среднем <tex>N/2</tex> мы перемещаем <tex>N/4</tex> элементов : <tex>O(C \cdot N \cdot (N/8+\log N)) = O(N^2/8)</tex>, следовательно <tex>C=1/8</tex>.
Анонимный участник

Навигация