http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=Xapdkop&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-29T05:05:49ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%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&diff=69936Сортировка вставками2019-02-24T12:13:40Z<p>Xapdkop: /* Двухпутевые вставки */ Ну и заодно подправил комментарии к шагам</p>
<hr />
<div>'''Сортировка вставками''' (англ. ''Insertion sort'') — квадратичный алгоритм [[Сортировка|сортировки]].<br />
<br />
==Алгоритм==<br />
Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.<br />
<br />
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве <tex>\displaystyle \frac {n(n - 1)} {2}</tex>.<br />
<br />
Алгоритм работает за <tex>O(n + k)</tex>, где <tex>k</tex> — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за <tex>O(n^2)</tex>. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.<br />
<br />
==Псевдокод==<br />
'''function''' insertionSort(a):<br />
'''for''' i = 1 '''to''' n - 1<br />
j = i - 1<br />
'''while''' j <tex> \geqslant </tex> 0 '''and''' a[j] > a[j + 1] <br />
swap(a[j], a[j + 1])<br />
j--<br />
<br />
==Пример работы==<br />
Пример работы алгоритма для массива <tex>[ 5, 2, 4, 3, 1 ]</tex><br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| До<br />
!style="background-color:#EEE"| После<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (проталкиваем второй элемент — '''''2''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''5 2''' 4 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 5''' 4 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| Алгоритм сравнивает второй элемент с первым и меняет их местами.<br />
|-<br />
|colspan=3|''Второй проход (проталкиваем третий элемент — '''''4''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''5 4''' 3 1 <br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 5''' 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| Сравнивает третий со вторым и меняет местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется<br />
|-<br />
|colspan=3|''Третий проход (проталкиваем четвертый — '''''3''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''5 3''' 1<br />
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''3 5''' 1<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 3''' 5 1<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 4''' 5 1<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1<br />
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется<br />
<br />
|-<br />
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''1''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''5 1'''<br />
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''1 5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет пятый и четвертый местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''4 1''' 5<br />
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''1 4''' 5<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 1''' 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''1 3''' 4 5 <br />
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 1''' 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| '''1 2''' 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет второй и первый местами. Массив отсортирован.<br />
|}<br />
== Оптимизации ==<br />
=== Бинарные вставки ===<br />
Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел. <br />
'''function''' insertionSort(a):<br />
'''for''' i = 1 '''to''' n - 1<br />
j = i - 1<br />
k = binSearch(a, a[i], 0, j)<br />
'''for''' m = j '''downto''' k<br />
swap(a[m], a[m+1])<br />
<br />
=== Двухпутевые вставки ===<br />
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается путём сдвига элементов влево или вправо туда, куда выгоднее.<br />
Пример для набора элементов <tex>[ 5, 7, 3, 4, 6 ]</tex> <br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| До<br />
!style="background-color:#EEE"| После<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (проталкиваем первый элемент — '''''5''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| <br />
|style="background-color:#FFF;padding:2px 30px"| '''5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов, то мы просто добавляем элемент туда.<br />
|-<br />
|colspan=3|''Второй проход (проталкиваем второй элемент — '''''7''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 30px"| 5 <br />
|style="background-color:#FFF;padding:2px 30px"| 5 '''7'''<br />
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и, так как позиция крайняя, то сдвигать ничего не приходится.<br />
|- <br />
|colspan=3|''Третий проход (проталкиваем третий — '''''3''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 30px"| 5 7<br />
|style="background-color:#FFF;padding:2px 20px"| '''3''' 5 7<br />
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и, так как позиция крайняя, то сдвигать ничего не приходится.<br />
|-<br />
|colspan=3|''Четвертый проход (проталкиваем четвертый элемент — '''''4''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 20px"| 3 5 7<br />
|style="background-color:#FFF;padding:2px 10px"| 3 '''4''' 5 7<br />
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше, чем до правого, значит сдвигаем левую часть.<br />
|-<br />
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''6''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 3 4 5 7<br />
|style="background-color:#FFF;padding:2px 10px"| 3 4 5 '''6''' 7<br />
|style="background-color:#FFF;padding:2px 10px"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.<br />
|} <br />
Как можно заметить структура поля вывода имеет сходство с [[Персистентный дек| деком]], а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего <tex>3</tex> элемента. Благодаря тому что для вставки <tex>j</tex>-ого элемента потребуется <tex>j/2</tex> сдвигов в худшем случае вместо <tex>j</tex>, то и итоговое число необходимых операций в худшем случае составит <tex>N^2 / 4 + N \log N</tex>.<br />
<br />
== См. также ==<br />
* [[Сортировка пузырьком]]<br />
* [[Сортировка выбором]]<br />
* [[Сортировка кучей]]<br />
* [[Сортировка слиянием]]<br />
* [[Быстрая сортировка]]<br />
* [[Сортировка подсчетом]]<br />
* [[Сортировка Шелла]]<br />
== Источники информации==<br />
* [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 Сортировка вставками]<br />
* Н. Вирт '''Алгоритмы и структуры данных''' {{---}} Невский Диалект, 2008. {{---}} 352 с. {{---}} ISBN 978-5-7940-0065-8<br />
* [http://rain.ifmo.ru/cat/view.php/vis/sorts/quadratic-2010 Визуализатор квадратичных алгоритмов]<br />
* [http://rain.ifmo.ru/cat/data/theory/school/ses-VectSort-03/pres.pdf Презентация «Сортировка вектора - 3. Insertion Sort»]<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]<br />
[[Категория: Квадратичные сортировки]]</div>Xapdkophttp://neerc.ifmo.ru/wiki/index.php?title=%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&diff=69935Сортировка вставками2019-02-24T12:05:44Z<p>Xapdkop: /* Двухпутевые вставки */ Исправлена нумерация элементов (для первых четырех съехала на плюс один)</p>
<hr />
<div>'''Сортировка вставками''' (англ. ''Insertion sort'') — квадратичный алгоритм [[Сортировка|сортировки]].<br />
<br />
==Алгоритм==<br />
Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.<br />
<br />
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве <tex>\displaystyle \frac {n(n - 1)} {2}</tex>.<br />
<br />
Алгоритм работает за <tex>O(n + k)</tex>, где <tex>k</tex> — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за <tex>O(n^2)</tex>. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.<br />
<br />
==Псевдокод==<br />
'''function''' insertionSort(a):<br />
'''for''' i = 1 '''to''' n - 1<br />
j = i - 1<br />
'''while''' j <tex> \geqslant </tex> 0 '''and''' a[j] > a[j + 1] <br />
swap(a[j], a[j + 1])<br />
j--<br />
<br />
==Пример работы==<br />
Пример работы алгоритма для массива <tex>[ 5, 2, 4, 3, 1 ]</tex><br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| До<br />
!style="background-color:#EEE"| После<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (проталкиваем второй элемент — '''''2''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''5 2''' 4 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 5''' 4 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| Алгоритм сравнивает второй элемент с первым и меняет их местами.<br />
|-<br />
|colspan=3|''Второй проход (проталкиваем третий элемент — '''''4''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''5 4''' 3 1 <br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 5''' 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| Сравнивает третий со вторым и меняет местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется<br />
|-<br />
|colspan=3|''Третий проход (проталкиваем четвертый — '''''3''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''5 3''' 1<br />
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''3 5''' 1<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 3''' 5 1<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 4''' 5 1<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1<br />
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется<br />
<br />
|-<br />
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''1''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''5 1'''<br />
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''1 5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет пятый и четвертый местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''4 1''' 5<br />
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''1 4''' 5<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 1''' 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''1 3''' 4 5 <br />
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 1''' 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| '''1 2''' 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет второй и первый местами. Массив отсортирован.<br />
|}<br />
== Оптимизации ==<br />
=== Бинарные вставки ===<br />
Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел. <br />
'''function''' insertionSort(a):<br />
'''for''' i = 1 '''to''' n - 1<br />
j = i - 1<br />
k = binSearch(a, a[i], 0, j)<br />
'''for''' m = j '''downto''' k<br />
swap(a[m], a[m+1])<br />
<br />
=== Двухпутевые вставки ===<br />
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается путём сдвига элементов влево или вправо туда, куда выгоднее.<br />
Пример для набора элементов <tex>[ 5, 7, 3, 4, 6 ]</tex> <br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| До<br />
!style="background-color:#EEE"| После<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (проталкиваем первый элемент — '''''5''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| <br />
|style="background-color:#FFF;padding:2px 30px"| '''5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов то мы просто добавляем элемент туда.<br />
|-<br />
|colspan=3|''Второй проход (проталкиваем второй элемент — '''''7''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 30px"| 5 <br />
|style="background-color:#FFF;padding:2px 30px"| 5 '''7'''<br />
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.<br />
|- <br />
|colspan=3|''Третий проход (проталкиваем третий — '''''3''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 30px"| 5 7<br />
|style="background-color:#FFF;padding:2px 20px"| '''3''' 5 7<br />
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.<br />
|-<br />
|colspan=3|''Четвертый проход (проталкиваем четвертый элемент — '''''4''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 20px"| 3 5 7<br />
|style="background-color:#FFF;padding:2px 10px"| 3 '''4''' 5 7<br />
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше ем до правого то сдвигаем левую часть.<br />
|-<br />
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''6''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 3 4 5 7<br />
|style="background-color:#FFF;padding:2px 10px"| 3 4 5 '''6''' 7<br />
|style="background-color:#FFF;padding:2px 10px"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.<br />
|} <br />
Как можно заметить структура поля вывода имеет сходство с [[Персистентный дек| деком]], а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего <tex>3</tex> элемента. Благодаря тому что для вставки <tex>j</tex>-ого элемента потребуется <tex>j/2</tex> сдвигов в худшем случае вместо <tex>j</tex>, то и итоговое число необходимых операций в худшем случае составит <tex>N^2 / 4 + N \log N</tex>.<br />
<br />
== См. также ==<br />
* [[Сортировка пузырьком]]<br />
* [[Сортировка выбором]]<br />
* [[Сортировка кучей]]<br />
* [[Сортировка слиянием]]<br />
* [[Быстрая сортировка]]<br />
* [[Сортировка подсчетом]]<br />
* [[Сортировка Шелла]]<br />
== Источники информации==<br />
* [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 Сортировка вставками]<br />
* Н. Вирт '''Алгоритмы и структуры данных''' {{---}} Невский Диалект, 2008. {{---}} 352 с. {{---}} ISBN 978-5-7940-0065-8<br />
* [http://rain.ifmo.ru/cat/view.php/vis/sorts/quadratic-2010 Визуализатор квадратичных алгоритмов]<br />
* [http://rain.ifmo.ru/cat/data/theory/school/ses-VectSort-03/pres.pdf Презентация «Сортировка вектора - 3. Insertion Sort»]<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]<br />
[[Категория: Квадратичные сортировки]]</div>Xapdkop