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

Материал из Викиконспекты
Перейти к: навигация, поиск
(исправлена опечатка "на на" -> "на")
 
(не показано 25 промежуточных версий 5 участников)
Строка 1: Строка 1:
'''Сортировка вставками''' — квадратичный алгоритм сортировки.
+
'''Сортировка вставками''' (англ. ''Insertion sort'') — квадратичный алгоритм [[Сортировка|сортировки]].
  
 
==Алгоритм==
 
==Алгоритм==
<wikitex>Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
+
Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
  
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве $\frac {n(n - 1)} {2}$.
+
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве <tex>\displaystyle \frac {n(n - 1)} {2}</tex>.
  
Алгоритм работает за $O(n + k)$, где k — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за $O(n^2)$. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.
+
Алгоритм работает за <tex>O(n + k)</tex>, где <tex>k</tex> — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за <tex>O(n^2)</tex>. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.
</wikitex>
 
  
 
==Псевдокод==
 
==Псевдокод==
  InsertionSort(a)
+
  '''function''' insertionSort(a):
   for i = 1 to n - 1:
+
   '''for''' i = 1 '''to''' n - 1
 
     j = i - 1
 
     j = i - 1
     while (j >= 0) and (a[j] > a[j + 1]):
+
     '''while''' j <tex>  \geqslant </tex> 0 '''and''' a[j] > a[j + 1]  
 
       swap(a[j], a[j + 1])
 
       swap(a[j], a[j + 1])
       j = j - 1
+
       j--
  
 
==Пример работы==
 
==Пример работы==
Пример работы алгоритма для массива [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"
Строка 76: Строка 75:
 
== Оптимизации ==
 
== Оптимизации ==
 
=== Бинарные вставки ===
 
=== Бинарные вставки ===
Так как в среднем количество сравнений для <tex>j</tex>-го элемента равно <tex>j/2</tex>, следовательно общее количество сравнений приблизительно <tex>\frac {(1+2+3+...+N)}{2} \approx N^2/4</tex>, но это очень много даже при малых <tex>N</tex>. Суть этого заключается в том, что поиск позиции для вставки <tex>j</tex>-го элемента осуществляется бинарным поиском, вследствие чего количество сравнений для <tex>N</tex> элементов <tex>N \cdot \log_{2} N</tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить <tex>R_j</tex> элемент на <tex>i</tex>-тое место, всё ещё необходимо переместить <tex>j-i</tex> элементов. В итоге время выполнения алгоритма уменьшилось в среднем в четыре раза : <tex>C \cdot N \cdot (N/4+log_{2} N) \approx N^2/4</tex>, следовательно <tex>C=1/4</tex>.
+
Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.  
  InsertionSort(a)
+
  '''function''' insertionSort(a):
   for i = 1 to n - 1:
+
   '''for''' i = 1 '''to''' n - 1
 
     j = i - 1
 
     j = i - 1
     k = BinSearch(a, a[i], 0, j)
+
     k = binSearch(a, a[i], 0, j)
       swap(a[k], a[i])
+
    '''for''' m = j '''downto''' k
     
+
       swap(a[m], a[m+1])
 +
 
 
=== Двухпутевые вставки ===
 
=== Двухпутевые вставки ===
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём сдвига элементов влево или вправо туда, куда выгоднее.
+
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается путём сдвига элементов влево или вправо туда, куда выгоднее.
Пример для набора элементов 5 7 3 4 6         
+
Пример для набора элементов <tex>[ 5, 7, 3, 4, 6 ]</tex>  
      5
+
{| style="background-color:#CCC;margin:0.5px"
      5 7
+
!style="background-color:#EEE"| До
    3 5 7
+
!style="background-color:#EEE"| После
  3 4 5 7
+
!style="background-color:#EEE"| Описание шага
  3 4 5 6 7
+
|-
Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в восемь раз : <tex>C \cdot N \cdot (N/8+log_{2} N) \approx N^2/8</tex>, следовательно <tex>C=1/8</tex>.
+
|colspan=3|''Первый проход (проталкиваем первый элемент — '''''5''''')''
+
|-
=== Метод Шелла ===
+
|style="background-color:#FFF;padding:2px 10px"|
Метод Шелла основан на том, что сортировка вставками более эффективна на маленьких или на частичной отсортированных входных данных. Устройство метода Шелла более понятно если рассматривать его на фиксированном наборе данных. Например мы имеем набор из 16 элементов <tex>R_1...R_{16}</tex> разобьём их на пары <tex>(R_1,R_9),...,(R_8,R_{16})</tex>. Каждое разделение называется проходом. Отсортируем каждую из пар. Разобьем на группы по 4 элемента <tex>(R_1,R_5,R_9,R_{13}),...,(R_4,R_8,R_{12},R_{16})</tex>. Отсортируем каждую из пар. Разобьём на 2 группы по восемь элементов <tex>(R_1,R_3,R_5,R_7,R_9,R_{11},R_{13},R_{15}),(R_2,R_4,R_6,R_8,R_{10},R_{12},R_{14},R_{16})</tex>. Отсортируем каждую из пар. При четвёртоми последнем проходе сортируются все 16 элементов. В итоге получится отсортированный массив.
+
|style="background-color:#FFF;padding:2px 30px"| '''5'''
Последовательность смещений 1 2 4 8 может меняться в зависимости от неё меняется и асимптотика. Например предложенная Хиббардом последовательность <tex>2^i-1 \le N, i \in N </tex> приводит к алгоритму с асимптотиткой <tex> O(N^{3/2}) </tex>.
+
|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов, то мы просто добавляем элемент туда.
 
+
|-
===Вставка в список ===
+
|colspan=3|''Второй проход (проталкиваем второй элемент — '''''7''''')''
При этой сортировке мы используем односвязной список вместо упорядоченной части массива. Теперь на не потребуется времени на сдвиг, а понадобиться всего лишь изменить родственные связи. При этом время выполнения сокращается в четыре раза : <tex>C \cdot N \cdot (N/4+2) \approx N^2/4</tex>, следовательно <tex>C=1/4</tex>.
+
|-
 
+
|style="background-color:#FFF;padding:2px 30px"| 5
=== Сортировка с вычислением адреса ===
+
|style="background-color:#FFF;padding:2px 30px"| 5 '''7'''
Сортировку с вычисление адреса выгодно использовать когда ключи распределены равномерно и не скапливаются хаотично в отдельных диапазонах значений. Вместо левой отсортированной части массива мы будем использовать <tex> M </tex> односвязных списков, в каждом из которых будут храниться значения из определённого диапазона. С каждым списком работаем как при простых выставках в список. Вероятность того что элемент попадёт в какой-либо список <tex>1/M</tex>, следовательно для каждого элемента происходит примерно <tex> \frac {N} {4 \cdot M} </tex> сравнений, следовательно общее количество сравнений <tex> \frac {N^2} {4 \cdot M} </tex>, а при <tex>M</tex> порядка <tex>N</tex> асимптотическая сложность уменьшается до <tex>O(N)</tex>.
+
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и, так как позиция крайняя, то сдвигать ничего не приходится.
Рассмотрим на примере.
+
|
Входные данные : 867 345 984 245 123 743 550 490 300
+
|colspan=3|''Третий проход (проталкиваем третий — '''''3''''')''
Будем использовать 4 списка с соответствующими диапазонами значений : 0 - 250, 251 - 500, 501 - 750, 751- 1000.
+
|-
{|border="1"
+
|style="background-color:#FFF;padding:2px 30px"| 5 7
|
+
|style="background-color:#FFF;padding:2px 20px"| '''3''' 5 7
|3 элемента
+
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и, так как позиция крайняя, то сдвигать ничего не приходится.
|6 элементов
+
|-
|9 элементов
+
|colspan=3|''Четвертый проход (проталкиваем четвертый элемент — '''''4''''')''
|-
+
|-
|0 - 250
+
|style="background-color:#FFF;padding:2px 20px"| 3 5 7
|
+
|style="background-color:#FFF;padding:2px 10px"| 3 '''4''' 5 7
|123 245
+
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше, чем до правого, значит сдвигаем левую часть.
|123 245
+
|-
|-
+
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''6''''')''
|251 - 500
+
|-
|345
+
|style="background-color:#FFF;padding:2px 10px"| 3 4 5 7
|345
+
|style="background-color:#FFF;padding:2px 10px"| 3 4 5 '''6''' 7
|300 345 490
+
|style="background-color:#FFF;padding:2px 10px"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.
|-
+
|}  
|501 - 750
+
Как можно заметить структура поля вывода имеет сходство с [[Персистентный дек| деком]], а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего <tex>3</tex> элемента. Благодаря тому что для вставки <tex>j</tex>-ого элемента потребуется <tex>j/2</tex> сдвигов в худшем случае вместо <tex>j</tex>, то и итоговое число необходимых операций в худшем случае составит <tex>N^2 / 4 + N \log N</tex>.
|
 
|743
 
|550 743
 
|-
 
|751 - 1000
 
|867 984
 
|867 984
 
|867 984
 
|}
 
 
 
== Сложность ==
 
Так как алгоритм сравнивает и меняет местами соседние элементы пока не найдёт подходящую позицию, то худший случай будет при входных данных отсортированных в обратном порядке.
 
  
 
== См. также ==
 
== См. также ==
Строка 142: Строка 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»]
 
* [http://rain.ifmo.ru/cat/data/theory/school/ses-VectSort-03/pres.pdf Презентация «Сортировка вектора - 3. Insertion Sort»]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировки]]
 
[[Категория: Сортировки]]
 +
[[Категория: Квадратичные сортировки]]

Текущая версия на 17:43, 9 февраля 2020

Сортировка вставками (англ. 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].

См. также[править]

Источники информации[править]