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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
  '''void''' insertionSort(a):
 
  '''void''' insertionSort(a):
 
   '''for''' i = 1 '''to''' n - 1
 
   '''for''' i = 1 '''to''' n - 1
     j--
+
     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 - 1
+
       j--
  
 
==Пример работы==
 
==Пример работы==
Строка 75: Строка 75:
 
== Оптимизации ==
 
== Оптимизации ==
 
=== Бинарные вставки ===
 
=== Бинарные вставки ===
Теперь вместо линейного поиска позиции мы будем использовать [http://ru.wikipedia.org/wiki/Двоичный_поиск Бинарный поиск], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма уменьшилось в среднем в два раза : <tex>N \cdot (N/4 + \log N) = N^2/4</tex>.
+
Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.  
 
  '''void''' insertionSort(a) :
 
  '''void''' insertionSort(a) :
 
   '''for''' i = 1 '''to''' n - 1
 
   '''for''' i = 1 '''to''' n - 1
     j--
+
     j = i - 1
 
     k = '''BinSearch'''(a, a[i], 0, j)
 
     k = '''BinSearch'''(a, a[i], 0, j)
     for m = j '''downto''' k
+
     '''for''' m = j '''downto''' k
       swap(a[j], a[j+1])
+
       swap(a[m], a[m+1])
 
        
 
        
 
=== Двухпутевые вставки ===
 
=== Двухпутевые вставки ===
Строка 121: Строка 121:
 
|style="background-color:#FFF;padding:2px 10px"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.
 
|style="background-color:#FFF;padding:2px 10px"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.
 
|}     
 
|}     
Как можно заметить структура поля вывода имеет сходство с [http://ru.wikipedia.org/wiki/Двусвязная_очередь Двусвязной очередью], а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в четыре раза, благодаря тому что теперь мы вместо перемещения в среднем <tex>N/2</tex> мы перемещаем <tex>N/4</tex> элементов : <tex>N \cdot (N/8+\log N) = N^2/8</tex>.  
+
Как можно заметить структура поля вывода имеет сходство с [[wikipedia:ru:Двусвязная очередь | двусвязной очередью]], а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в четыре раза, благодаря тому что теперь мы вместо перемещения в среднем <tex>N/2</tex> мы перемещаем <tex>N/4</tex> элементов : <tex>N \cdot (N/8+\log N) = N^2/8</tex>.  
 
   
 
   
  
Строка 133: Строка 133:
 
* [[Сортировка Шелла]]
 
* [[Сортировка Шелла]]
 
== Источники ==
 
== Источники ==
* [http://ru.wikipedia.org/wiki/Сортировка_вставками Сортировка вставками Википедия]
+
* [[wikipedia:ru:Сортировка вставками|Сортировка вставками {{---}} Википедия]]
 
* Н. Вирт «Алгоритмы и структуры данных», часть 2.2.1 "Сортировка с помощью прямого включения"
 
* Н. Вирт «Алгоритмы и структуры данных», часть 2.2.1 "Сортировка с помощью прямого включения"
 
== Дополнительные материалы ==
 
== Дополнительные материалы ==

Версия 22:08, 4 июня 2014

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

Алгоритм

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

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

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

Псевдокод

void 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]. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.

void 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 Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.

Как можно заметить структура поля вывода имеет сходство с двусвязной очередью, а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в четыре раза, благодаря тому что теперь мы вместо перемещения в среднем [math]N/2[/math] мы перемещаем [math]N/4[/math] элементов : [math]N \cdot (N/8+\log N) = N^2/8[/math].


См. также

Источники

Дополнительные материалы