97
правок
Изменения
м
Категории
==Сортировка с однопоточным слиянием==
Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.
'''function ''' mergeSortMT(array, left, right):
mid = (left + right) / 2
merge(array, left, mid, right)
В данном алгоритме оператор <tex>\mathrm {\bf {spawn}}</tex> запускает новый поток, а оператор <tex>\mathrm {\bf {sync}}</tex> ожидает завершения этого потока. Функция <tex>\mathrm {merge}</tex> аналогична одноименной функции из раздела [[Сортировка слиянием#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5_.D0.B4.D0.B2.D1.83.D1.85_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.BE.D0.B2|слияние двух массивов]].<br>
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: <tex dpi="120">T(n) = T(\frac {n}{2}) + \Theta(n) = \Theta(n)</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>
// если <tex dpi="120">x \leqslant T[left]</tex>, возвращает <tex dpi="120">left</tex>
// иначе возвращает наибольший индекс <tex dpi="120">i</tex> из отрезка <tex dpi="120">[left, right]</tex> такой, что <tex dpi="120">array[i - 1] < x</tex>
'''integer ''' binarySearch(x, array, left, right)
// слияние <tex dpi="120">T[left_{1} \dots right_{1}]</tex> и <tex dpi="120">T[left_{2} \dots right_{2}]</tex> в <tex dpi="120">A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}]</tex>
'''function ''' mergeMT(T, left<tex dpi="120">_{1}</tex>, right<tex dpi="120">_{1}</tex>, left<tex dpi="120">_{2}</tex>, right<tex dpi="120">_{2}</tex>, A, left<tex dpi="120">_{3}</tex>):
n<tex dpi="120">_{1}</tex> = right<tex dpi="120">_{1}</tex> - left<tex dpi="120">_{1}</tex> + 1
n<tex dpi="120">_{2}</tex> = right<tex dpi="120">_{2}</tex> - left<tex dpi="120">_{2}</tex> + 1
Приведем псевдокод алгоритма, использующего слияние из предыдущего раздела, сортирующего элементы <tex dpi="120">A[leftA \dots rightA]</tex> и помещающего отсортированный массив в <tex dpi="120">B[leftB \dots leftB + rightA - leftA]</tex>
'''function ''' mergeSortMT2(A, leftA, rightA, B, leftB):
n = r - p + 1
'''if''' n == 1
==Источники информации==
*Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. {{---}} Introduction to Algorithms, Third Edition
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка]]
