Изменения

Parallel Sorting by Regular Sampling {{---}} параллельная сортировка, разработанная Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет два преимущества по сравнению с [[Быстрая сортировка|быстрой сортировкой]]:

* сохраняет размер списка более сбалансированным на протяжении всего процесса

* избегает повторных перестановок ключей

* Начало.

* '''Шаг 1.''' Исходный массив в <tex>n</tex> элементов разделим поровну между <tex>p</tex> процессорами.

* Конец.

Количество элементов <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| Презентация]

[[Категория:Дискретная математика и алгоритмы]]

[[Категория:Сортировка]]