Редактирование: Сортировка вставками

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Сортировка вставками''' (англ. ''Insertion sort'') — квадратичный алгоритм [[Сортировка|сортировки]].
+
'''Сортировка вставками''' — квадратичный алгоритм сортировки.
  
 
==Алгоритм==
 
==Алгоритм==
Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
+
<wikitex>Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
  
 
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве <tex>\displaystyle \frac {n(n - 1)} {2}</tex>.
 
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве <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>
  
 
==Псевдокод==
 
==Псевдокод==
  '''function''' insertionSort(a):
+
  '''InsertionSort'''(a)
   '''for''' i = 1 '''to''' n - 1
+
   '''for''' i = 1 to n - 1:
 
     j = i - 1
 
     j = i - 1
     '''while''' j <tex>  \geqslant </tex> 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 = j - 1
  
 
==Пример работы==
 
==Пример работы==
Пример работы алгоритма для массива <tex>[ 5, 2, 4, 3, 1 ]</tex>
+
Пример работы алгоритма для массива <tex>5, 2, 4, 3, 1</tex>
  
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
Строка 75: Строка 76:
 
== Оптимизации ==
 
== Оптимизации ==
 
=== Бинарные вставки ===
 
=== Бинарные вставки ===
Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.  
+
Так как в среднем количество сравнений для <tex>j</tex>-го элемента равно <tex>j/2</tex>, следовательно общее количество сравнений приблизительно <tex>\displaystyle \frac {(1+2+3+...+N)}{2} = N^2/4</tex>, но это очень много даже при малых <tex>N</tex>. Суть этого заключается в том, что поиск позиции для вставки <tex>j</tex>-го элемента осуществляется бинарным поиском, вследствие чего количество сравнений для <tex>N</tex> элементов <tex> N\log N </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить <tex>R_j</tex> элемент на <tex>i</tex>-тое место, всё ещё необходимо переместить <tex>j-i</tex> элементов. В итоге время выполнения алгоритма уменьшилось в среднем в четыре раза : <tex>O(C \cdot N \cdot (N/8+\log N)) = O(N^2/4)</tex>, следовательно <tex>C=1/4</tex>.
  '''function''' insertionSort(a):
+
  '''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)
    '''for''' m = j '''downto''' k
+
      '''swap'''(a[k], a[i])
      swap(a[m], a[m+1])
+
     
 
 
 
=== Двухпутевые вставки ===
 
=== Двухпутевые вставки ===
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается путём сдвига элементов влево или вправо туда, куда выгоднее.
+
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём сдвига элементов влево или вправо туда, куда выгоднее.
Пример для набора элементов <tex>[ 5, 7, 3, 4, 6 ]</tex>     
+
Пример для набора элементов <tex>5, 7, 3, 4, 6</tex>     
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
 
!style="background-color:#EEE"| До
 
!style="background-color:#EEE"| До
Строка 91: Строка 91:
 
!style="background-color:#EEE"| Описание шага
 
!style="background-color:#EEE"| Описание шага
 
|-
 
|-
|colspan=3|''Первый проход (проталкиваем первый элемент — '''''5''''')''
+
|colspan=3|''Первый проход (проталкиваем второй элемент — '''''5''''')''
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 10px"|  
 
|style="background-color:#FFF;padding:2px 10px"|  
|style="background-color:#FFF;padding:2px 30px"| '''5'''
+
|style="background-color:#FFF;padding:2px 10px"| '''5'''
|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов, то мы просто добавляем элемент туда.
+
|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов то мы просто добавляем элемент туда.
 
|-
 
|-
|colspan=3|''Второй проход (проталкиваем второй элемент — '''''7''''')''
+
|colspan=3|''Второй проход (проталкиваем третий элемент — '''''7''''')''
 
|-
 
|-
|style="background-color:#FFF;padding:2px 30px"| 5  
+
|style="background-color:#FFF;padding:2px 10px"| 5  
|style="background-color:#FFF;padding:2px 30px"| 5 '''7'''
+
|style="background-color:#FFF;padding:2px 10px"| 5 '''7'''
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и, так как позиция крайняя, то сдвигать ничего не приходится.
+
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.
 
|-   
 
|-   
|colspan=3|''Третий проход (проталкиваем третий — '''''3''''')''
+
|colspan=3|''Третий проход (проталкиваем четвертый — '''''3''''')''
 
|-
 
|-
|style="background-color:#FFF;padding:2px 30px"| 5 7
+
|style="background-color:#FFF;padding:2px 10px"| 5 7
|style="background-color:#FFF;padding:2px 20px"| '''3''' 5 7
+
|style="background-color:#FFF;padding:2px 10px"| '''3''' 5 7
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и, так как позиция крайняя, то сдвигать ничего не приходится.
+
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.
 
|-
 
|-
|colspan=3|''Четвертый проход (проталкиваем четвертый элемент — '''''4''''')''
+
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''4''''')''
 
|-
 
|-
|style="background-color:#FFF;padding:2px 20px"| 3 5 7
+
|style="background-color:#FFF;padding:2px 10px"| 3 5 7
 
|style="background-color:#FFF;padding:2px 10px"| 3 '''4''' 5 7
 
|style="background-color:#FFF;padding:2px 10px"| 3 '''4''' 5 7
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше, чем до правого, значит сдвигаем левую часть.
+
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше ем до правого то сдвигаем левую часть.
 
|-
 
|-
 
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''6''''')''
 
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''6''''')''
Строка 121: Строка 121:
 
|style="background-color:#FFF;padding:2px 10px"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.
 
|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>.
+
Как можно заметить структура поля вывода имеет сходство с Двусвязной очередью, а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в восемь раз, благодаря тому что теперь мы вместо перемещения в среднем <tex>N/2</tex> мы перемещаем <tex>N/4</tex> элементов : <tex>O(C \cdot N \cdot (N/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)</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 \cdot M} </tex>, а при <tex>M</tex> порядка <tex>N</tex> асимптотическая сложность уменьшается до <tex>O(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
 +
|}
 +
 
 +
== Сложность ==
 +
Так как алгоритм сравнивает и меняет местами соседние элементы пока не найдёт подходящую позицию, то худший случай будет при входных данных отсортированных в обратном порядке.
  
 
== См. также ==
 
== См. также ==
Строка 131: Строка 169:
 
* [[Сортировка подсчетом]]
 
* [[Сортировка подсчетом]]
 
* [[Сортировка Шелла]]
 
* [[Сортировка Шелла]]
== Источники информации==
+
== Источники ==
* [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 Сортировка вставками]
+
* [http://ru.wikipedia.org/wiki/Сортировка_вставками Сортировка вставками — Википедия]
* Н. Вирт '''Алгоритмы и структуры данных''' {{---}} Невский Диалект, 2008. {{---}} 352 с. {{---}} ISBN 978-5-7940-0065-8
+
* Н. Вирт «Алгоритмы и структуры данных», часть 2.2.1 "Сортировка с помощью прямого включения"
 +
== Дополнительные материалы ==
 
* [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»]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировки]]
 
[[Категория: Сортировки]]
[[Категория: Квадратичные сортировки]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: