Изменения

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

На вход подаётся * Начало.* '''Шаг 1.''' Исходный массив в <tex>n</tex> элементов. Для начала надо разделить входные данные на разделим поровну между <tex>p</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.''' Формируем массив разделителей из него p разделителей с элементов вспомогательного массива под индексами <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.''' Данные из процессоров поочерёдно записываем в исходный массив. Данные отсортированы.* Конец.

|style="background-color:#FFF;padding:2px 10px"| После слитияслияния

При <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>p</tex> массивов в каждом процессоре. Также мы должны помнить, учитывая что при равномерном распределении данных длина сливаемых массивов будет <tex dpi=145>\frac {n}{p^2}</tex>, а <tex>\mathrm {merge} </tex> двух массивов выполняется за сумму их длин, это . Поэтому <tex>\mathrm {merge} </tex> займёт <tex dpi=145> O(\sum \limits_{k=2}^{p} \frac {k \cdot n}{p^2})=O(\frac {n \cdot p \cdot (p+1)}{2p^2}-\frac {n}{p^2})=O(n)</tex>. В итоге мы получим Откуда получаем итоговую асимптотику: <tex dpi=145> O(\frac {n\log(n/p)}{p})+O(p^2\log(p))+O(n)+O(p)</tex> Что равно:  <tex dpi=145> =O(\frac {n\log(n/p)}{p}+p^2\log(p)+\frac {n}{p\log p}+p)=O(\frac {n\log(n/p)}{p})</tex>.