Изменения

Перейти к: навигация, поиск

Обсуждение:PSRS-сортировка

43 байта добавлено, 03:42, 11 июня 2014
Нет описания правки
=== Алгоритм ===
Для начала надо разделить входные данные на n равных частей, где <tex>n</tex> {{---}} количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами <tex>0,\frac {n} {p^2}, \frac {2n}{p^2},...,\frac {(p-1)n}{p^2}</tex> и элементы стоящие в процессорах левее выбранных. Далее на нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами <tex>\displaystyle p + [\frac {p} {2}] - 1, 2p + [\frac {p}{2}] - 1,...,(p-1)p + [\frac {p}{2}] - 1</tex>. Теперь разделим данные в процессорах согласно полученному массиву разделителей.
Пусть <tex>a_1, a_2,..., a_j</tex> разделители, элементы . Данные в каждом процессоре разобьём не группы элементов, попадающие в соответствующие полу-интервалы <tex>(-\infty,a_1],(a_1,a_2],...,(a_j,+\infty)</tex>. Далее с сольём соответствующие группы, которые отсортированы по в возрастанию, в массивы. Слияние будем производить поочерёдно, то есть сначала сольём первую группу со второй потом результат с третей и так далее. В итоге получим отсортированный набор данных.
=== Пример ===
Количество элементов <tex>27</tex>, количество процессоров <tex>3</tex>.
|}
=== Анализ ===
При <tex>n</tex> элементах и <tex>p</tex> процессорах начальная сортировка выполнится за <tex>O(\displaystyle \frac {n}{p\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>\displaystyle\frac {n}{p^2}</tex>< , а merge двух массивов выполняется за сумму их длин, это займёт <tex>\displaystyle O(\sum \limits_{k=12}^{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>\displaystyle O(\frac {n}{p\log(n/p)}{p})+O(p^2\log(p))+O(n)+O(p)</tex><tex>\displaystyle =O(\frac {n}{p\log(n/p)}{p}+p^2\log(p)+\frac {n}{p\log p}+p)=O(\frac {n\log(n/p)}{p})</tex>.
=== См. также ===
[[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием]]
77
правок

Навигация