Изменения

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

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

5 байт убрано, 21:57, 11 июня 2014
Алгоритм
=== Алгоритм ===
Для начала надо разделить входные данные на <tex>n</tex> равных частей, где <tex>n</tex> {{---}} количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами <tex>0,\frac {n} {p^2}, \frac {2n}{p^2},...,\frac {(p-1)n}{p^2}</tex> и элементы стоящие в процессорах левее выбранных. Далее Теперь на нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами <tex> 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>. Далее сольём соответствующие группы, которые отсортированы по в возрастанию, в массивы. Слияние будем производить поочерёдно, то есть сначала сольём первую группу со второй потом результат с третей и так далее. В итоге получим отсортированный набор данных.
=== Пример ===
77
правок

Навигация