Последовательный алгоритм
Последовательный алгоритм быстрой сортировки
основан на операции последовательного разделения сортируемого набора данных на
блоки меньшего размера таким образом, что между значениями разных блоков
обеспечивается отношение упорядоченности: для любых двух блоков найдётся блок,
все значения которого меньше значений второго блока. На первой итерации метода
производится деление исходной последовательности данных на первые две части -
для осуществления этого деления в последовательности выбирается некоторый
ведущий элемент (pivot) и все значения набора, меньшие ведущего элемента
или равные ему, переносятся в первый формируемый блок, все остальные значения
составляют второй блок последовательности. На последующих итерациях сортировки
описанная выше схема применяется последовательно для каждого из вновь
сформированных блоков. После выполнения log n (n - число элементов исходной
последовательности) итераций исходный массив будет упорядочен.
Параллельный алгоритм
Существует несколько параллельных обобщений алгоритма быстрой сортировки,
в зависимости от топологии вычислительной системы, на которой решается задача.
Рассмотрим наиболее простое из этих обобщений - для вычислительной системы с
топологией в виде D - мерного гиперкуба, т.е. p=2D. Пусть исходный набор данных (N - элементов) распределён между всеми p процессорами блоками одинакового размера
N/p. После окончания работы алгоритма
мы должны получить расположение блоков, соответствующее нумерации процессоров
(вершин) гиперкуба. При таких начальных условиях первая итерация параллельного
алгоритма состоит в следующем:
- из общего набора данных каким-либо образом выбрать ведущий элемент и разослать по всем процессорам
вычислительной системы;
- разделить на каждом процессоре имеющийся блок данных на два подблока
согласно полученному ведущему элементу (деление осуществляется способом аналогичным описанному для
последовательной реализации);
- образовать пары процессоров, номера которых
различаются лишь значением в бите D, затем произвести взаимообмен
данными во всех полученных парах процессоров. В результате такого обмена
данными на процессорах, D-ый бит которых
равен 0, должны содержаться части блоков со значениями меньшими , либо равными
значению ведущего элемента, процессоры же с номерами, содержащими 1 в
D-ом бите, должны содержать все значения
превышающие значение ведущего элемента
.
В результате
выполнения такой итерации сортировки исходный набор данных оказывается
разделённым на две части, одна из которых (со значениями меньшими или равными
значению ведущего элемента) располагается на процессорах, в битовом
представлении номеров которых бит D равен 0.
Нетрудно понять, что таких процессоров ровно p/2 и, следовательно, D-мерный гиперкуб оказывается разделённым на два
гиперкуба, размерность каждого из которых
равна D-1. К этим гиперкубам, в свою очередь, может быть применена
описанная выше процедура. После D-кратного
повторения таких итераций для получения отсортированной последовательности
данных достаточно упорядочить блоки получившиеся на каждом процессоре
вычислительной системы.
