Обсуждение:PSRS-сортировка — различия между версиями
AlexeyL (обсуждение | вклад) |
AlexeyL (обсуждение | вклад) |
||
Строка 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. Теперь разделим данные в процессорах согласно полученному массиву разделителей и сольём данные соответствующие части в в массив.
Пример:
Пример:
Описание команды | 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 |