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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 123: Строка 123:
 
Как можно заметить структура поля вывода имеет сходство с Двусвязной очередью, а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 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>.  
 
Как можно заметить структура поля вывода имеет сходство с Двусвязной очередью, а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 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
 
|}
 
  
 
== См. также ==
 
== См. также ==

Версия 01:43, 4 июня 2014

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

Алгоритм

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

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

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

Псевдокод

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 = j - 1

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

Пример работы алгоритма для массива [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]j[/math]-го элемента равно [math]j/2[/math], следовательно общее количество сравнений приблизительно [math]\displaystyle \frac {(1+2+3+...+N)}{2} = N^2/4[/math], но это очень много даже при малых [math]N[/math]. Суть этого заключается в том, что поиск позиции для вставки [math]j[/math]-го элемента осуществляется бинарным поиском, вследствие чего количество сравнений для [math]N[/math] элементов [math] N\log N [/math]. Количество сравнений заметно уменьшилось, но для того, чтобы поставить [math]R_j[/math] элемент на [math]i[/math]-тое место, всё ещё необходимо переместить [math]j-i[/math] элементов. В итоге время выполнения алгоритма уменьшилось в среднем в два раза : [math]O(C \cdot N \cdot (N/4 + \log N)) = O(N^2/4)[/math], следовательно [math]C=1/4[/math].

InsertionSort'(a)
  for i = 1 to n - 1:
    j = i - 1
    k = BinSearch(a, a[i], 0, j)
      swap(a[k], a[i])
      

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

Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём сдвига элементов влево или вправо туда, куда выгоднее. Пример для набора элементов [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]O(C \cdot N \cdot (N/8+\log N)) = O(N^2/8)[/math], следовательно [math]C=1/8[/math].


См. также

Источники

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