Обсуждение:PSRS-сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
=== Алгоритм ===
 
=== Алгоритм ===
 
Для начала надо разделить входные данные на 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. Теперь разделим данные в процессорах согласно полученному массиву разделителей и сольём данные соответствующие части в в массив.
 
Для начала надо разделить входные данные на 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. Теперь разделим данные в процессорах согласно полученному массиву разделителей и сольём данные соответствующие части в в массив.
 +
 +
Пример:
 +
 +
[[Файл:img010.GIF]]
 +
 +
 +
Пример:
 +
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| Описание команды
 +
!style="background-color:#EEE"| 1 процессор
 +
!style="background-color:#EEE"| 2 процессор
 +
!style="background-color:#EEE"| 3 процессор
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Разделение между процессорами
 +
|style="background-color:#FFF;padding:2px 10px"| 6 3 7 3 8 9 5 1 3 9 0 4 7 4 3
 +
|style="background-color:#FFF;padding:2px 10px"| 7 8 2 4 1 0 6 3 7 8 3 9 3 6 5
 +
|style="background-color:#FFF;padding:2px 10px"| 8 9 0 4 3 2 5 1 5 7 3 9 4 2 7
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| После сортировки частей
 +
|style="background-color:#FFF;padding:2px 10px"| 0 1 3 3 3 3 4 4 5 6 7 7 8 9 9
 +
|style="background-color:#FFF;padding:2px 10px"| 0 1 2 3 3 3 4 5 6 6 7 7 8 8 9
 +
|style="background-color:#FFF;padding:2px 10px"| 0 1 2 2 3 3 4 4 5 5 7 7 8 9 9
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Выбор элементов
 +
|style="background-color:#FFF;padding:2px 10px"| '''0''' 1 3 3 '''3 3''' 4 4 5 '''6 7''' 7 8 9 '''9'''
 +
|style="background-color:#FFF;padding:2px 10px"| '''0''' 1 2 3 '''3 3''' 4 5 6 '''6 7''' 7 8 8 '''9'''
 +
|style="background-color:#FFF;padding:2px 10px"| '''0''' 1 2 2 '''3 3''' 4 4 5 '''5 7''' 7 8 9 '''9'''
 +
|}
 +
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| Описание команды
 +
!style="background-color:#EEE"| Данные
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Выбранные элементы
 +
|style="background-color:#FFF;padding:2px 10px"| 6 8 9 9 0 3 7 1 0 8 3 5 8 3 2 7 3 7
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| После сортировки
 +
|style="background-color:#FFF;padding:2px 10px"| 0 0 0 3 3 3 3 3 3 5 6 6 7 7 7 9 9 9
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Выбор элементов
 +
|style="background-color:#FFF;padding:2px 10px"| 0 0 0 3 3 '''3''' 3 3 3 5 6 '''6''' 7 7 7 9 9 '''9'''
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Разделители
 +
|style="background-color:#FFF;padding:2px 10px"| 3 6 9
 +
|}
 +
 +
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| Описание команды
 +
!style="background-color:#EEE"| 1 процессор
 +
!style="background-color:#EEE"| 1 процессор
 +
!style="background-color:#EEE"| 1 процессор
 +
!style="background-color:#EEE"| 2 процессор
 +
!style="background-color:#EEE"| 2 процессор
 +
!style="background-color:#EEE"| 2 процессор
 +
!style="background-color:#EEE"| 3 процессор
 +
!style="background-color:#EEE"| 3 процессор
 +
!style="background-color:#EEE"| 3 процессор
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| После сортировки частей
 +
|style="background-color:#FFF;padding:2px 10px"| 0 1 3 3 3 3
 +
|style="background-color:#FFF;padding:2px 10px"| 4 4 5 6
 +
|style="background-color:#FFF;padding:2px 10px"| 7 7 8 9 9
 +
|style="background-color:#FFF;padding:2px 10px"| 0 1 2 3 3 3
 +
|style="background-color:#FFF;padding:2px 10px"| 4 5 6 6
 +
|style="background-color:#FFF;padding:2px 10px"| 7 7 8 8 9
 +
|style="background-color:#FFF;padding:2px 10px"| 0 1 2 2 3 3
 +
|style="background-color:#FFF;padding:2px 10px"| 4 4 5 5
 +
|style="background-color:#FFF;padding:2px 10px"| 7 7 8 9 9
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| После обмена данными
 +
|style="background-color:#FFF;padding:2px 10px"| 0 1 3 3 3 3
 +
|style="background-color:#FFF;padding:2px 10px"| 0 1 2 3 3 3
 +
|style="background-color:#FFF;padding:2px 10px"| 0 1 2 2 3 3
 +
|style="background-color:#FFF;padding:2px 10px"| 4 4 5 6
 +
|style="background-color:#FFF;padding:2px 10px"| 4 5 6 6
 +
|style="background-color:#FFF;padding:2px 10px"| 4 4 5 5
 +
|style="background-color:#FFF;padding:2px 10px"| 7 7 8 9 9
 +
|style="background-color:#FFF;padding:2px 10px"| 7 7 8 8 9
 +
|style="background-color:#FFF;padding:2px 10px"| 7 7 8 9 9

Версия 22:10, 10 июня 2014

Сортировка 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. Теперь разделим данные в процессорах согласно полученному массиву разделителей и сольём данные соответствующие части в в массив.

Пример:

Img010.GIF


Пример:

Описание команды 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 процессор 1 процессор 1 процессор 2 процессор 2 процессор 2 процессор 3 процессор 3 процессор 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
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение:PSRS-сортировка&oldid=38396»