Обсуждение:PSRS-сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
'''Сортировка вставками''' — квадратичный алгоритм сортировки.
+
==Распараллеливание простых сортировок==
 
+
===Параллельная сортировка пузырьком===
==Алгоритм==
+
Сначала главный процессор разбивает исходный массив длиной <tex>z</tex> элементов на <tex>p</tex> равных частей блоков. Каждый блок содержит <tex>p=z/n</tex> элементов массива. Полученные блоки рассылаются по процессам. Далее идет предобработка. На этапе предобработки каждый процесс сортирует свой массив методом пузырьковой сортировки. Далее происходит чередование чет-нечетных перестановок на p итерациях. На нечетной итерации пары процессов с номерами <tex>(0,1)(2,3)(4,5)…</tex> обмениваются друг с другом массивами, при этом выполняется слияние блоков, после чего на процессе с меньшим номером остается <tex>n/p</tex> первых упорядоченных элементов объединенного массива, а на процессе с большим номером остается <tex>n/p</tex> последних упорядоченных элементов объединенного массива. На четной итерации происходит все точно так же, но обмен производится между процессами с номерами <tex>(1,2)(3,4)(5,6)(7,8)</tex> . Если в течении двух последовательных четной и нечетной итерации не производится никаких изменений, то алгоритм может прекратить свою работу заранее. После этого части массивов отсылаются на главный процесс и там объединяются, после чего получается отсортированный массив. Предобработка занимет <tex>p^2</tex> тактов после чего происходит максимум <tex>n</tex> слияний. Осознать, что максимально количество слияний можно, представив частный случай. Пусть минимальный элемент оказался в последнем блоке тогда за за каждое слияние он будет перемещаться на один блок влево. После <tex>n</tex> слияний он окажется в первом блоке. В итоге время сортировки сократится с <tex> z^2 </tex> до <tex> p^2+2pn\log (2*p)</tex> .
<wikitex>Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
 
 
 
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве <tex>\displaystyle \frac {n(n - 1)} {2}</tex>.
 
 
 
Алгоритм работает за $O(n + k)$, где k — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за $O(n^2)$. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.
 
</wikitex>
 
 
 
==Псевдокод==
 
'''InsertionSort'''(a)
 
  '''for''' i = 1 to n - 1:
 
    j = i - 1
 
    '''while''' (j <tex> \geqslant </tex> 0) and (a[j] > a[j + 1]):
 
      '''swap'''(a[j], a[j + 1])
 
      j = j - 1
 
 
 
==Пример работы==
 
Пример работы алгоритма для массива <tex>5, 2, 4, 3, 1</tex>
 
 
 
{| style="background-color:#CCC;margin:0.5px"
 
!style="background-color:#EEE"| До
 
!style="background-color:#EEE"| После
 
!style="background-color:#EEE"| Описание шага
 
|-
 
|colspan=3|''Первый проход (проталкиваем второй элемент — '''''2''''')''
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| '''5 2''' 4 3 1
 
|style="background-color:#FFF;padding:2px 10px"| '''2 5''' 4 3 1
 
|style="background-color:#FFF;padding:2px 10px"| Алгоритм сравнивает второй элемент с первым и меняет их местами.
 
|-
 
|colspan=3|''Второй проход (проталкиваем третий элемент — '''''4''''')''
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| 2 '''5 4''' 3 1
 
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 5''' 3 1
 
|style="background-color:#FFF;padding:2px 10px"| Сравнивает третий со вторым и меняет местами
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1
 
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1
 
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется
 
|-
 
|colspan=3|''Третий проход (проталкиваем четвертый — '''''3''''')''
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''5 3''' 1
 
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''3 5''' 1
 
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 3''' 5 1
 
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 4''' 5 1
 
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1
 
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1
 
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется
 
 
 
|-
 
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''1''''')''
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''5 1'''
 
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''1 5'''
 
|style="background-color:#FFF;padding:2px 10px"| Меняет пятый и четвертый местами
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''4 1''' 5
 
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''1 4''' 5
 
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 1''' 4 5
 
|style="background-color:#FFF;padding:2px 10px"| 2 '''1 3''' 4 5
 
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| '''2 1''' 3 4 5
 
|style="background-color:#FFF;padding:2px 10px"| '''1 2''' 3 4 5
 
|style="background-color:#FFF;padding:2px 10px"| Меняет второй и первый местами. Массив отсортирован.
 
|}
 
== Оптимизации ==
 
=== Бинарные вставки ===
 
Так как в среднем количество сравнений для <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/4 + \log N)) = O(N^2/4)</tex>, следовательно <tex>C=1/4</tex>
 
'''InsertionSort''''(a)
 
  '''for''' i = 1 to n - 1:
 
    j = i - 1
 
    k = '''BinSearch'''(a, a[i], 0, j)
 
      '''swap'''(a[k], a[i])
 
     
 
=== Двухпутевые вставки ===
 
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём сдвига элементов влево или вправо туда, куда выгоднее.
 
Пример для набора элементов <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 10px"| '''5'''
 
|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов то мы просто добавляем элемент туда.
 
|-
 
|colspan=3|''Второй проход (проталкиваем третий элемент — '''''7''''')''
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| 5  
 
|style="background-color:#FFF;padding:2px 10px"| 5 '''7'''
 
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.
 
|- 
 
|colspan=3|''Третий проход (проталкиваем четвертый — '''''3''''')''
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| 5 7
 
|style="background-color:#FFF;padding:2px 10px"| '''3''' 5 7
 
|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.
 
|-
 
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''4''''')''
 
|-
 
|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"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше ем до правого то сдвигаем левую часть.
 
|-
 
|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"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.
 
|}   
 
Как можно заметить структура поля вывода имеет сходство с Двусвязной очередью, а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 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
 
|}
 
 
 
== См. также ==
 
* [[Сортировка пузырьком]]
 
* [[Сортировка выбором]]
 
* [[Сортировка кучей]]
 
* [[Сортировка слиянием]]
 
* [[Быстрая сортировка]]
 
* [[Сортировка подсчетом]]
 
* [[Сортировка Шелла]]
 
== Источники ==
 
* [http://ru.wikipedia.org/wiki/Сортировка_вставками Сортировка вставками — Википедия]
 
* Н. Вирт «Алгоритмы и структуры данных», часть 2.2.1 "Сортировка с помощью прямого включения"
 
== Дополнительные материалы ==
 
* [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»]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировки]]
 

Версия 17:50, 9 июня 2014

Распараллеливание простых сортировок

Параллельная сортировка пузырьком

Сначала главный процессор разбивает исходный массив длиной [math]z[/math] элементов на [math]p[/math] равных частей блоков. Каждый блок содержит [math]p=z/n[/math] элементов массива. Полученные блоки рассылаются по процессам. Далее идет предобработка. На этапе предобработки каждый процесс сортирует свой массив методом пузырьковой сортировки. Далее происходит чередование чет-нечетных перестановок на p итерациях. На нечетной итерации пары процессов с номерами [math](0,1)(2,3)(4,5)…[/math] обмениваются друг с другом массивами, при этом выполняется слияние блоков, после чего на процессе с меньшим номером остается [math]n/p[/math] первых упорядоченных элементов объединенного массива, а на процессе с большим номером остается [math]n/p[/math] последних упорядоченных элементов объединенного массива. На четной итерации происходит все точно так же, но обмен производится между процессами с номерами [math](1,2)(3,4)(5,6)(7,8)…[/math] . Если в течении двух последовательных четной и нечетной итерации не производится никаких изменений, то алгоритм может прекратить свою работу заранее. После этого части массивов отсылаются на главный процесс и там объединяются, после чего получается отсортированный массив. Предобработка занимет [math]p^2[/math] тактов после чего происходит максимум [math]n[/math] слияний. Осознать, что максимально количество слияний можно, представив частный случай. Пусть минимальный элемент оказался в последнем блоке тогда за за каждое слияние он будет перемещаться на один блок влево. После [math]n[/math] слияний он окажется в первом блоке. В итоге время сортировки сократится с [math] z^2 [/math] до [math] p^2+2pn\log (2*p)[/math] .