Последовательный алгоритм
Метод основывается на последовательном разделении сортируемого набора данных на блоки меньшего размера таким образом, что между значениями разных блоков обеспечивается отношение упорядоченности (для любой пары блоков все значения одного из этих блоков не превышают значений другого блока). На первой итерации метода осуществляется деление исходного набора данных на первые две части – для организации такого деления выбирается некоторый ведущий элемент и все значения набора, меньшие ведущего элемента, переносятся в первый формируемый блок, все остальные значения образуют второй блок набора. На второй итерации сортировки, описанные правила применяются рекурсивно для обоих сформированных блоков и т.д. При надлежащем выборе ведущих элементов после выполнения log₂n итераций исходный массив данных оказывается упорядоченным.
Параллельный алгоритм
Существует несколько параллельных обобщений последовательного алгоритма быстрой сортировки. Применим простой способ, наиболее подходящий для кластерных систем с большим количеством процессоров(N).
Пусть, исходный набор данных расположен на первом процессоре, с него начинается ускорение алгоритма:
- процессор выбирает ведущий элемент и оставляет слева меньшие элементы, справа большие;
- всю меньшую часть он отдаёт другому процессору;
- отдав меньшую часть, процессор продолжает работать с большей одновременно с другим процессом, который работает с меньшей по принципу начиная с 1го пункта;
- Когда все N процессоров получат свою часть, ускорение алгоритма будет максимальным.
В результате выполнения такой итерации сортировки, исходный набор оказывается разделенным на две части (случайно), меньшая из которых передаётся другому процессору, большая остаётся на исходном для дальнейших итераций, в результате следующей итерации обе части опять будут разделены и опять на двух исходных останятся большие части (на первом процессоре всё равно бОльшая), а меньшие отправятся новым процессам. В этом заключается ускорение алгоритма. При зодействовании всех процессов, все части параллельно будут сортироваться последовательным алгоритмом.
Такой алгоритм даёт максимальное ускорение на многопроцессорных системах (кластерах, суперкомпьютерах).
Однако есть и минус этого алгоритма. Принцип быстрой сортировки в том, что массив делится случайно на 2 части и редко пололам. Процессоры, получающие меньшие части, закончат с ними сортировку быстрее, первый исходный (главный) процессор и будут простаивать. Алгоритм нуждается в модификации.
