Участник:Ashabokov 415/Алгоритм быстрой сортировки

Алгоритм быстрой сортировки

Свойства и структура алгоритмов

Общее описание алгоритма

Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров [math]\displaystyle{ p = 2^n }[/math]. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины [math]\displaystyle{ n }[/math], следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером [math]\displaystyle{ n_1 }[/math] процессору номер [math]\displaystyle{ n_2 }[/math], где [math]\displaystyle{ n_1 }[/math] отличается от [math]\displaystyle{ n_2 }[/math] только в n-том разряде двоичного представления, в двоичном представлении числа [math]\displaystyle{ n_1 }[/math] на n-той позиции стоит 1, а [math]\displaystyle{ n_2 }[/math] — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

Математическое описание алгоритма

Очевидно, что наиболее медленной операцией в описанной выше схеме является операция обмена данными между процессорами, следовательно, хотелось бы получить некоторую оценку количества обменов. Такая оценка приведена ниже:

[math]\displaystyle{ \sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p }[/math] ,

где [math]\displaystyle{ p }[/math] — количество задействованных процессоров.