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

Материал из Викиконспекты
Перейти к: навигация, поиск

Сортировка PSRS

Алгоритм

Для начала надо разделить входные данные на n равных частей, где n - количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами 0, n/p^2, 2n/p^2,...,(p-1)n/p^2 и элементы стоящие в процессорах левее выбранных. Далее на нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами p + [p / 2] - 1, 2p + [p / 2] - 1,...,(p-1)n + [p / 2] - 1. Теперь разделим данные в процессорах согласно полученному массиву разделителей и сольём данные соответствующие части в в массив.