77
правок
Изменения
Нет описания правки
Parallel Sorting by Regular Sampling {{---}} параллельная сортировка, разработанная Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет два преимущества по сравнению с [[Быстрая сортировка|быстрой сортировкой]]:
* сохраняет размер списка более сбалансированным на протяжении всего процесса
* избегает повторных перестановок ключей
* Начало.
* '''Шаг 1.''' Исходный массив в <tex>n</tex> элементов разделим поровну между <tex>p</tex> процессорами.
* '''Шаг 2.''' На каждом процессоре запускам [[Быстрая сортировка|быструю сортировку]].* '''Шаг 3.''' Формируем вспомогательный массив из элементов каждого процессора под индексами <tex dpi=145>0,\frac {n} {p^2}, \frac {2n}{p^2},...,\frac {(p-1)n}{p^2}</tex>.* '''Шаг 4.''' Сортируем вспомогательный массив с помощью быстрой сортировки.* '''Шаг 5.''' Формируем массив разделителей из элементов вспомогательного массива под индексами <tex dpi=145> p + [\frac {p} {2}] - 1, 2p + [\frac {p}{2}] - 1,...,(p-1)p + [\frac {p}{2}] - 1</tex>.* '''Шаг 6.''' Делим данные в процессорах с помощью массива разделителей следующим образом. Пусть <tex>a_1, a_2,..., a_j</tex> {{---}} разделители. Тогда данные в каждом процессоре разобьём на группы элементов, попадающие в соответствующие полуинтервалы <tex>(-\infty,a_1],(a_1,a_2],...,(a_j,+\infty)</tex>.* '''Шаг 7.''' Сливаем соответствующие группы элементов в массивы. Слияние будем производить поочерёдно, то есть сначала сольём первую группу со второй потом результат с третей и так далее. В итоге получим отсортированный набор данных.* '''Шаг 8.''' Данные из процессоров поочерёдно записываем в исходный массив. Данные отсортированы.
* Конец.
Количество элементов <tex>27</tex>, количество процессоров <tex>3</tex>.
Исходный набор данных:
|}
При <tex>n</tex> элементах и <tex>p</tex> процессорах начальная сортировка выполнится за <tex dpi=145>O( \frac {n\log(n/p)}{p})</tex>. Выбор порядка <tex>p</tex> элементов в каждом процессоре произойдёт за <tex>O(p)</tex>, их сортировать мы будем с помощью [[Быстрая сортировка|быстрой сортировки]], а так же учитывая, что их количество порядка <tex>p</tex>, то можно сказать, что они сортируются за <tex>O(p^2\log(p^2))=O(p^2\log(p))</tex>.
<tex dpi=145>O(\frac {n\log(n/p)}{p}+p^2\log(p)+n+p)=O(\frac {n\log(n/p)}{p})</tex>.
* [[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием]]
* [[Быстрая сортировка|Быстрая сортировка]]
* [https://wiki.engr.illinois.edu/download/attachments/99155993/Sort+ParaProg(Quinn)chpt14.5.pdf?version=1&modificationDate=1203641170000| Статья о PSRS]
* [http://users.cms.caltech.edu/~cs284/lectures/29oct97/sld003.htm| Презентация]
