Изменения

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

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

2429 байт убрано, 9 февраль
исправлена опечатка "на на" -> "на"
'''Сортировка вставками''' (англ. ''Insertion sort'') — квадратичный алгоритм [[Сортировка|сортировки]].
==Алгоритм==
<wikitex>Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве <tex>\displaystyle \frac {n(n - 1)} {2}</tex>.
Алгоритм работает за $<tex>O(n + k)$</tex>, где <tex>k </tex> — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за $<tex>O(n^2)$</tex>. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.</wikitex>
==Псевдокод==
'''InsertionSortfunction'''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 {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>случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел. '''InsertionSort'function'''insertionSort(a): '''for''' i = 1 '''to ''' n - 1:
j = i - 1
k = '''BinSearch'''binSearch(a, a[i], 0, j) '''for''' m = j '''swapdownto'''k swap(a[km], a[im+1])
=== Двухпутевые вставки ===
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём путём сдвига элементов влево или вправо туда, куда выгоднее.Пример для набора элементов <tex>[ 5, 7, 3, 4, 6]</tex>
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| До
!style="background-color:#EEE"| Описание шага
|-
|colspan=3|''Первый проход (проталкиваем второй первый элемент — '''''5''''')''
|-
|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"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше ем , чем до правого то , значит сдвигаем левую часть.
|-
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''6''''')''
|style="background-color:#FFF;padding:2px 10px"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.
|}
Как можно заметить структура поля вывода имеет сходство с Двусвязной очередью[[Персистентный дек| деком]], а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в четыре раза, благодаря тому что теперь мы вместо перемещения в среднем <tex>N/23</tex> мы перемещаем элемента. Благодаря тому что для вставки <tex>N/4j</tex> элементов : -ого элемента потребуется <tex>O(C \cdot N \cdot (Nj/8+\log N)) = O(N^2/8)</tex>, следовательно <tex>C=1/8</tex>. ===Вставка сдвигов в список ===При этой сортировке мы используем односвязной список худшем случае вместо упорядоченной части массива. Теперь на не потребуется времени на сдвиг, а понадобиться всего лишь изменить родственные связи. При этом время выполнения сокращается в два раза : <tex>O(C \cdot N \cdot (N/4+2) ) = O( N^2/4)j</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 + N \cdot M} </tex>, а при <tex>M</tex> порядка <tex>N</tex> асимптотическая сложность уменьшается до <tex>O(log 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" | |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/Сортировка_вставками %D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%B0%D0%BC%D0%B8 Сортировка вставками — Википедия]* Н. Вирт «Алгоритмы '''Алгоритмы и структуры данных»данных''' {{---}} Невский Диалект, часть 22008.2{{---}} 352 с.1 "Сортировка с помощью прямого включения"== Дополнительные материалы =={{---}} ISBN 978-5-7940-0065-8
* [http://rain.ifmo.ru/cat/view.php/vis/sorts/quadratic-2010 Визуализатор квадратичных алгоритмов]
* [http://rain.ifmo.ru/cat/data/theory/school/ses-VectSort-03/pres.pdf Презентация «Сортировка вектора - 3. Insertion Sort»]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Квадратичные сортировки]]
Анонимный участник

Навигация