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

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

Сортировка PSRS

Алгоритм

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

Пример

Количество элементов 45, количество процессоров 3. Исходный набор данных [math][6, 3, 7, 3, 8, 9, 5, 1, 3, 9, 0, 4, 7, 4, 3, 7, 8, 2, 4, 1, 0, 6, 3, 7, 8, 3, 9, 3, 6, 5, 8, 9, 0, 4, 3, 2, 5, 1, 5, 7, 3, 9, 4, 2, 7][/math]:

Описание команды 1 процессор 2 процессор 3 процессор
Разделение между процессорами 6 3 7 3 8 9 5 1 3 9 0 4 7 4 3 7 8 2 4 1 0 6 3 7 8 3 9 3 6 5 8 9 0 4 3 2 5 1 5 7 3 9 4 2 7
После сортировки частей 0 1 3 3 3 3 4 4 5 6 7 7 8 9 9 0 1 2 3 3 3 4 5 6 6 7 7 8 8 9 0 1 2 2 3 3 4 4 5 5 7 7 8 9 9
Выбор элементов 0 1 3 3 3 3 4 4 5 6 7 7 8 9 9 0 1 2 3 3 3 4 5 6 6 7 7 8 8 9 0 1 2 2 3 3 4 4 5 5 7 7 8 9 9
Описание команды Данные
Выбранные элементы 6 8 9 9 0 3 7 1 0 8 3 5 8 3 2 7 3 7
После сортировки 0 0 0 3 3 3 3 3 3 5 6 6 7 7 7 9 9 9
Выбор элементов 0 0 0 3 3 3 3 3 3 5 6 6 7 7 7 9 9 9
Разделители 3 6 9

В данном примере для удобства были выбраны другие элементы.

Описание команды 1 процессор 2 процессор 3 процессор
После сортировки частей 0 1 3 3 3 3 4 4 5 6 7 7 8 9 9 0 1 2 3 3 3 4 5 6 6 7 7 8 8 9 0 1 2 2 3 3 4 4 5 5 7 7 8 9 9
После обмена данными 0 1 3 3 3 3 0 1 2 3 3 3 0 1 2 2 3 3 4 4 5 6 4 5 6 6 4 4 5 5 7 7 8 9 9 7 7 8 8 9 7 7 8 9 9
После слития 0 0 0 1 1 1 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 5 5 5 5 6 6 6 7 7 7 7 7 7 8 8 8 8 9 9 9 9 9

Анализ

При [math]n[/math] элементах и [math]p[/math] процессорах начальная сортировка выполнится за [math]O(n/p\log(n/p))[/math]. Выбор порядка [math]p[/math] элементов в каждом процессоре произойдёт за [math]O(p)[/math],их сортировка произойдёт за [math]O(p^2\log(p^2))=O(p^2\log(p))[/math]. После обмена данными будет произведено слияние [math]p[/math] массивов в каждом процессоре, это займёт [math]O(n/p\log p)[/math]. В итоге мы получаем [math]O(n/p\log(n/p))+O(p^2\log(p))+O(n/p\log p)+O(p)[/math][math]=O(n/p\log(n/p)+p^2\log(p)+n/p\log p+p)=O(n/p\log(n/p))[/math]