PSRS-сортировка
Версия от 22:30, 11 июня 2014; AlexeyL (обсуждение | вклад)
Содержание
Описание
Parallel Sorting by Regular Sampling — параллельная сортировка, разработанная Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет два преимущества по сравнению с быстрой сортировкой:
- сохраняет размер списка более сбалансированным на протяжении всего процесса
- избегает повторных перестановок ключей
Алгоритм
На вход подаётся
элементов. Для начала надо разделить входные данные на равных частей, где — количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами . Теперь нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами . После чего разделим данные в процессорах согласно полученному массиву разделителей. Пусть — разделители. Разделение происходит следующим образом, данные в каждом процессоре разобьём на группы элементов, попадающие в соответствующие полуинтервалы . Далее сольём соответствующие группы, которые отсортированы по в возрастанию, в массивы. Слияние будем производить поочерёдно, то есть сначала сольём первую группу со второй потом результат с третей и так далее. В итоге получим отсортированный набор данных.Пример
Количество элементов
, количество процессоров . Исходный набор данных::
Описание этапа | 1 процессор | 2 процессор | 3 процессор |
---|---|---|---|
Разделение между процессорами | 15 46 48 93 39 6 72 91 14 | 36 69 40 89 61 97 12 21 54 | 53 97 84 58 32 27 33 72 20 |
После сортировки частей | 6 14 15 39 46 48 72 91 93 | 12 21 36 40 54 61 69 89 97 | 20 27 32 33 53 58 72 84 97 |
Выбор элементов | 6 14 15 39 46 48 72 91 93 | 12 21 36 40 54 61 69 89 97 | 20 27 32 33 53 58 72 84 97 |
Описание этапа | Данные |
---|---|
Выбранные элементы | 6 39 72 12 40 69 20 33 72 |
После сортировки | 6 12 20 33 39 40 69 72 72 |
Выбор элементов | 6 12 20 33 39 40 69 72 72 |
Разделители | 33 69 |
Описание этапа | 1 процессор | 2 процессор | 3 процессор | ||||||
---|---|---|---|---|---|---|---|---|---|
После сортировки частей | 6 14 15 | 39 46 48 | 72 91 93 | 12 21 | 36 40 54 61 69 | 89 97 | 20 27 32 33 | 53 58 | 72 84 97 |
После обмена данными | 6 14 15 | 12 21 | 20 27 32 33 | 39 46 48 | 36 40 54 61 69 | 53 58 | 72 91 93 | 89 97 | 72 84 97 |
После слития | 6 12 14 | 15 20 21 | 27 32 33 | 36 39 40 | 46 48 53 | 54 58 61 69 | 72 72 | 84 89 91 | 93 97 97 |
Анализ
При
элементах и процессорах начальная сортировка выполнится за . Выбор порядка элементов в каждом процессоре произойдёт за ,их сортировать мы будем с помощью быстрой сортировки, а так же учитывая что их количество порядка , то можно сказать, что они сортируются за . После обмена данными будет произведено слияние массивов в каждом процессоре, учитывая что при равномерном распределении данных длина сливаемых массивов будет , а двух массивов выполняется за сумму их длин, это займёт . В итоге мы получим .