Сортировка вставками — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 39 промежуточных версий 9 участников)
Строка 1: Строка 1:
'''Сортировка вставками''' — квадратичный алгоритм сортировки.
+
'''Сортировка вставками''' (англ. ''Insertion sort'') — квадратичный алгоритм [[Сортировка|сортировки]].
  
 
==Алгоритм==
 
==Алгоритм==
<wikitex>На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
+
Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
 +
 
 +
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве <tex>\displaystyle \frac {n(n - 1)} {2}</tex>.
 +
 
 +
Алгоритм работает за <tex>O(n + k)</tex>, где <tex>k</tex> — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за <tex>O(n^2)</tex>. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.
  
Алгоритм работает за $O(n + k)$, где k — число обменов элементов входного массива. В среднем и в худшем случае — за $O(n^2)$. Более точные оценки работы алгоритма приведены ниже.
 
</wikitex>
 
 
==Псевдокод==
 
==Псевдокод==
<wikitex>
+
'''function''' insertionSort(a):
for (int i = 1; i $\leqslant$ n - 1; i++)
+
  '''for''' i = 1 '''to''' n - 1
     j $\leftarrow$ i - 1
+
     j = i - 1
     while (j $\geqslant$ 0 && a[j] > a[j + 1])
+
     '''while''' j <tex>  \geqslant </tex> 0 '''and''' a[j] > a[j + 1]  
        a[j] $\leftrightarrow$ a[j + 1]
+
      swap(a[j], a[j + 1])
        j $\leftarrow$ j - 1
+
      j--
</wikitex>
 
== Анализ алгоритма ==
 
<wikitex>Число сравнений ключей на i-ом просеивании ключей ($C_i$) самое большее равно $i-1$, самое меньшее — 1; если предположить, что все перестановки из $n$ ключей равновероятны, то среднее число сравнений $i/2$. Число же обменов элементов $M_i$ равно равно $C_i+2$. Поэтому общее число сравнений и число обменов таковы:
 
  
{| border="0"
 
!style="background-color:#FFF"| $C_{best} = n-1$
 
|width=5%|&nbsp;
 
!style="background-color:#FFF"| $M_{best} = 3(n-1)$
 
|-
 
!style="background-color:#FFF"| $C_{average} = (n^2+n-2)/4$
 
|
 
!style="background-color:#FFF"| $M_{average} = (n^2+9n-10)/4$
 
|-
 
!style="background-color:#FFF"| $C_{worst} = (n^2+n-4)/4$
 
|
 
!style="background-color:#FFF"| $M_{worst} = (n^2+3n-4)/2$
 
|}
 
Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.</wikitex>
 
 
==Пример работы==
 
==Пример работы==
Пример работы алгоритма для массива [5, 2, 4, 3, 1]
+
Пример работы алгоритма для массива <tex>[ 5, 2, 4, 3, 1 ]</tex>
  
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
Строка 88: Строка 73:
 
|style="background-color:#FFF;padding:2px 10px"| Меняет второй и первый местами. Массив отсортирован.
 
|style="background-color:#FFF;padding:2px 10px"| Меняет второй и первый местами. Массив отсортирован.
 
|}
 
|}
 +
== Оптимизации ==
 +
=== Бинарные вставки ===
 +
Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.
 +
'''function''' insertionSort(a):
 +
  '''for''' i = 1 '''to''' n - 1
 +
    j = i - 1
 +
    k = binSearch(a, a[i], 0, j)
 +
    '''for''' m = j '''downto''' k
 +
      swap(a[m], a[m+1])
 +
 +
=== Двухпутевые вставки ===
 +
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается путём сдвига элементов влево или вправо туда, куда выгоднее.
 +
Пример для набора элементов <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 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"| 3 4 5 7
 +
|style="background-color:#FFF;padding:2px 10px"| 3 4 5 '''6''' 7
 +
|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>.
 +
 
== См. также ==
 
== См. также ==
 
* [[Сортировка пузырьком]]
 
* [[Сортировка пузырьком]]
Строка 95: Строка 130:
 
* [[Быстрая сортировка]]
 
* [[Быстрая сортировка]]
 
* [[Сортировка подсчетом]]
 
* [[Сортировка подсчетом]]
== Источники ==
+
* [[Сортировка Шелла]]
* [http://ru.wikipedia.org/wiki/Сортировка_вставками Википедия - свободная энциклопедия]
+
== Источники информации==
* Н. Вирт «Алгоритмы и структуры данных», часть 2.2.1 "Сортировка с помощью прямого включения"
+
* [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 Сортировка вставками]
== Дополнительные материалы ==
+
* Н. Вирт '''Алгоритмы и структуры данных''' {{---}} Невский Диалект, 2008. {{---}} 352 с. {{---}} ISBN 978-5-7940-0065-8
 
* [http://rain.ifmo.ru/cat/view.php/vis/sorts/quadratic-2010 Визуализатор квадратичных алгоритмов]
 
* [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»]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировки]]
 
[[Категория: Сортировки]]
 +
[[Категория: Квадратичные сортировки]]

Текущая версия на 19:28, 4 сентября 2022

Сортировка вставками (англ. Insertion sort) — квадратичный алгоритм сортировки.

Алгоритм

Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.

Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число инверсий на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве [math]\displaystyle \frac {n(n - 1)} {2}[/math].

Алгоритм работает за [math]O(n + k)[/math], где [math]k[/math] — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за [math]O(n^2)[/math]. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.

Псевдокод

function insertionSort(a):
  for i = 1 to n - 1
    j = i - 1
    while j [math]  \geqslant [/math] 0 and a[j] > a[j + 1] 
      swap(a[j], a[j + 1])
      j--

Пример работы

Пример работы алгоритма для массива [math][ 5, 2, 4, 3, 1 ][/math]

До После Описание шага
Первый проход (проталкиваем второй элемент — 2)
5 2 4 3 1 2 5 4 3 1 Алгоритм сравнивает второй элемент с первым и меняет их местами.
Второй проход (проталкиваем третий элемент — 4)
2 5 4 3 1 2 4 5 3 1 Сравнивает третий со вторым и меняет местами
2 4 5 3 1 2 4 5 3 1 Второй и первый отсортированы, swap не требуется
Третий проход (проталкиваем четвертый — 3)
2 4 5 3 1 2 4 3 5 1 Меняет четвертый и третий местами
2 4 3 5 1 2 3 4 5 1 Меняет третий и второй местами
2 3 4 5 1 2 3 4 5 1 Второй и первый отсортированы, swap не требуется
Четвертый проход (проталкиваем пятый элемент — 1)
2 3 4 5 1 2 3 4 1 5 Меняет пятый и четвертый местами
2 3 4 1 5 2 3 1 4 5 Меняет четвертый и третий местами
2 3 1 4 5 2 1 3 4 5 Меняет третий и второй местами
2 1 3 4 5 1 2 3 4 5 Меняет второй и первый местами. Массив отсортирован.

Оптимизации

Бинарные вставки

Теперь вместо линейного поиска позиции мы будем использовать бинарный поиск, следовательно количество сравнений изменится с [math]O(N^2)[/math] до [math] O(N\log N) [/math]. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.

function insertionSort(a):
  for i = 1 to n - 1
    j = i - 1
    k = binSearch(a, a[i], 0, j)
    for m = j downto k
      swap(a[m], a[m+1])

Двухпутевые вставки

Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается путём сдвига элементов влево или вправо туда, куда выгоднее. Пример для набора элементов [math][ 5, 7, 3, 4, 6 ][/math]

До После Описание шага
Первый проход (проталкиваем первый элемент — 5)
5 Так как в поле вывода нет элементов, то мы просто добавляем элемент туда.
Второй проход (проталкиваем второй элемент — 7)
5 5 7 С помощью Бинарного поиска находим позицию и, так как позиция крайняя, то сдвигать ничего не приходится.
Третий проход (проталкиваем третий — 3)
5 7 3 5 7 С помощью Бинарного поиска находим позицию и, так как позиция крайняя, то сдвигать ничего не приходится.
Четвертый проход (проталкиваем четвертый элемент — 4)
3 5 7 3 4 5 7 С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше, чем до правого, значит сдвигаем левую часть.
Четвертый проход (проталкиваем пятый элемент — 6)
3 4 5 7 3 4 5 6 7 Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.

Как можно заметить структура поля вывода имеет сходство с деком, а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего [math]3[/math] элемента. Благодаря тому что для вставки [math]j[/math]-ого элемента потребуется [math]j/2[/math] сдвигов в худшем случае вместо [math]j[/math], то и итоговое число необходимых операций в худшем случае составит [math]N^2 / 4 + N \log N[/math].

См. также

Источники информации