Изменения
исправлена опечатка "на на" -> "на"
'''Сортировка вставками''' (англ. ''Insertion sort'') — квадратичный алгоритм [[Сортировка|сортировки]].
==Алгоритм==
==Псевдокод==
'''voidfunction''' insertionSort(a):
'''for''' i = 1 '''to''' n - 1
j = i - 1
== Оптимизации ==
=== Бинарные вставки ===
Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел. '''voidfunction''' insertionSort(a) :
'''for''' i = 1 '''to''' n - 1
j = i - 1
k = '''BinSearch'''binSearch(a, a[i], 0, j)
'''for''' m = j '''downto''' k
swap(a[m], a[m+1])
=== Двухпутевые вставки ===
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается путём сдвига элементов влево или вправо туда, куда выгоднее.
!style="background-color:#EEE"| Описание шага
|-
|colspan=3|''Первый проход (проталкиваем второй первый элемент — '''''5''''')''
|-
|style="background-color:#FFF;padding:2px 10px"|
|style="background-color:#FFF;padding:2px 30px"| '''5'''
|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов , то мы просто добавляем элемент туда.
|-
|colspan=3|''Второй проход (проталкиваем третий второй элемент — '''''7''''')''
|-
|style="background-color:#FFF;padding:2px 30px"| 5
|style="background-color:#FFF;padding:2px 30px"| 5 '''7'''
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и , так как позиция крайняя , то сдвигать ничего не приходится.
|-
|colspan=3|''Третий проход (проталкиваем четвертый третий — '''''3''''')''
|-
|style="background-color:#FFF;padding:2px 30px"| 5 7
|style="background-color:#FFF;padding:2px 20px"| '''3''' 5 7
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и , так как позиция крайняя , то сдвигать ничего не приходится.
|-
|colspan=3|''Четвертый проход (проталкиваем пятый четвертый элемент — '''''4''''')''
|-
|style="background-color:#FFF;padding:2px 20px"| 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"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.
|}
Как можно заметить структура поля вывода имеет сходство с [[Персистентный дек| деком]], а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего <tex>3 </tex> элемента. Благодаря тому что для вставки <tex>j</tex>-ого элемента потребуется <tex>j/2</tex> сдвигов в худшем случае вместо <tex>j</tex>, то и итоговая асимптотика итоговое число необходимых операций в худшем случае составит <tex>N^2 / 4 + N \log N</tex>.
== См. также ==
* [[Сортировка подсчетом]]
* [[Сортировка Шелла]]
== Источники информации==* [[wikipediahttp://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»]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Квадратичные сортировки]]
