Алговики - Вклад [ru]

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

2019-12-02T15:08:42Z

Ashabokov 415: /* Существующие реализации алгоритма */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пусть для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, а правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше, в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами больше или равными опорному.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>. <ref> https://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка </ref>

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — <math>0</math>. Таким образом, после данной операции все данные будут разделены между процессорами, образующими <math>n-1</math>-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из <math>n-1</math>-мерных кубов, получим 4 <math>n-2</math>-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости:

1. По числу процессоров: 1.0581. Это значит, что с увеличением количества задействованных процессоров эффективность увеличивается. Такое поведение можно объяснить тем, что при увеличении числа процессоров размер сортируемого участка массива для каждого отдельного процессора уменьшается.

2. По числу входных данных: -0.6059. Это значит, что с ростом размеров входных данных эффективность алгоритма падает. Это можно объяснить тем, что при алгоритм предполагает многократный обмен массивами данных, а это значит, что при увеличении размера задачи накладные расходы на обмен данными между процессорами тоже сильно возрастает.

3. По двум направлениям: 0.0386. Это значит, что с ростом числа процессоров и размерами входных данных эффективность все же возрастает, но скорость не слишком велика.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Язык программирования Java содержит реализацию данного алгоритма в библиотеке java.util.<ref>https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html </ref> Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T15:08:10Z

Ashabokov 415: /* Существующие реализации алгоритма */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пусть для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, а правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше, в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами больше или равными опорному.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>. <ref> https://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка </ref>

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — <math>0</math>. Таким образом, после данной операции все данные будут разделены между процессорами, образующими <math>n-1</math>-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из <math>n-1</math>-мерных кубов, получим 4 <math>n-2</math>-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости:

1. По числу процессоров: 1.0581. Это значит, что с увеличением количества задействованных процессоров эффективность увеличивается. Такое поведение можно объяснить тем, что при увеличении числа процессоров размер сортируемого участка массива для каждого отдельного процессора уменьшается.

2. По числу входных данных: -0.6059. Это значит, что с ростом размеров входных данных эффективность алгоритма падает. Это можно объяснить тем, что при алгоритм предполагает многократный обмен массивами данных, а это значит, что при увеличении размера задачи накладные расходы на обмен данными между процессорами тоже сильно возрастает.

3. По двум направлениям: 0.0386. Это значит, что с ростом числа процессоров и размерами входных данных эффективность все же возрастает, но скорость не слишком велика.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Язык программирования Java содержит реализацию данного алгоритма в библиотеке java.util. Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T14:53:56Z

Ashabokov 415: /* Информационный граф */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пусть для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, а правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше, в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами больше или равными опорному.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>. <ref> https://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка </ref>

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — <math>0</math>. Таким образом, после данной операции все данные будут разделены между процессорами, образующими <math>n-1</math>-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из <math>n-1</math>-мерных кубов, получим 4 <math>n-2</math>-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости:

1. По числу процессоров: 1.0581. Это значит, что с увеличением количества задействованных процессоров эффективность увеличивается. Такое поведение можно объяснить тем, что при увеличении числа процессоров размер сортируемого участка массива для каждого отдельного процессора уменьшается.

2. По числу входных данных: -0.6059. Это значит, что с ростом размеров входных данных эффективность алгоритма падает. Это можно объяснить тем, что при алгоритм предполагает многократный обмен массивами данных, а это значит, что при увеличении размера задачи накладные расходы на обмен данными между процессорами тоже сильно возрастает.

3. По двум направлениям: 0.0386. Это значит, что с ростом числа процессоров и размерами входных данных эффективность все же возрастает, но скорость не слишком велика.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T14:53:29Z

Ashabokov 415: /* Информационный граф */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пусть для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, а правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше, в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами больше или равными опорному.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>. <ref> https://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка </ref>

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими <math>n-1</math>-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из <math>n-1</math>-мерных кубов, получим 4 <math>n-2</math>-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости:

1. По числу процессоров: 1.0581. Это значит, что с увеличением количества задействованных процессоров эффективность увеличивается. Такое поведение можно объяснить тем, что при увеличении числа процессоров размер сортируемого участка массива для каждого отдельного процессора уменьшается.

2. По числу входных данных: -0.6059. Это значит, что с ростом размеров входных данных эффективность алгоритма падает. Это можно объяснить тем, что при алгоритм предполагает многократный обмен массивами данных, а это значит, что при увеличении размера задачи накладные расходы на обмен данными между процессорами тоже сильно возрастает.

3. По двум направлениям: 0.0386. Это значит, что с ростом числа процессоров и размерами входных данных эффективность все же возрастает, но скорость не слишком велика.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T14:48:37Z

Ashabokov 415: /* Схема реализации последовательного алгоритма */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пусть для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, а правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше, в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами больше или равными опорному.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>. <ref> https://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка </ref>

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости:

1. По числу процессоров: 1.0581. Это значит, что с увеличением количества задействованных процессоров эффективность увеличивается. Такое поведение можно объяснить тем, что при увеличении числа процессоров размер сортируемого участка массива для каждого отдельного процессора уменьшается.

2. По числу входных данных: -0.6059. Это значит, что с ростом размеров входных данных эффективность алгоритма падает. Это можно объяснить тем, что при алгоритм предполагает многократный обмен массивами данных, а это значит, что при увеличении размера задачи накладные расходы на обмен данными между процессорами тоже сильно возрастает.

3. По двум направлениям: 0.0386. Это значит, что с ростом числа процессоров и размерами входных данных эффективность все же возрастает, но скорость не слишком велика.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T14:47:41Z

Ashabokov 415: /* Схема реализации последовательного алгоритма */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пусть для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, а правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше, в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами больше или равным опорному.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>. <ref> https://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка </ref>

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости:

1. По числу процессоров: 1.0581. Это значит, что с увеличением количества задействованных процессоров эффективность увеличивается. Такое поведение можно объяснить тем, что при увеличении числа процессоров размер сортируемого участка массива для каждого отдельного процессора уменьшается.

2. По числу входных данных: -0.6059. Это значит, что с ростом размеров входных данных эффективность алгоритма падает. Это можно объяснить тем, что при алгоритм предполагает многократный обмен массивами данных, а это значит, что при увеличении размера задачи накладные расходы на обмен данными между процессорами тоже сильно возрастает.

3. По двум направлениям: 0.0386. Это значит, что с ростом числа процессоров и размерами входных данных эффективность все же возрастает, но скорость не слишком велика.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T14:47:08Z

Ashabokov 415: /* Схема реализации последовательного алгоритма */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пусть для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, а правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше, в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами больше (или равным) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>. <ref> https://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка </ref>

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости:

1. По числу процессоров: 1.0581. Это значит, что с увеличением количества задействованных процессоров эффективность увеличивается. Такое поведение можно объяснить тем, что при увеличении числа процессоров размер сортируемого участка массива для каждого отдельного процессора уменьшается.

2. По числу входных данных: -0.6059. Это значит, что с ростом размеров входных данных эффективность алгоритма падает. Это можно объяснить тем, что при алгоритм предполагает многократный обмен массивами данных, а это значит, что при увеличении размера задачи накладные расходы на обмен данными между процессорами тоже сильно возрастает.

3. По двум направлениям: 0.0386. Это значит, что с ростом числа процессоров и размерами входных данных эффективность все же возрастает, но скорость не слишком велика.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T14:44:14Z

Ashabokov 415: /* Макроструктура алгоритма */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пусть для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, а правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше, в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>. <ref> https://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка </ref>

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости:

1. По числу процессоров: 1.0581. Это значит, что с увеличением количества задействованных процессоров эффективность увеличивается. Такое поведение можно объяснить тем, что при увеличении числа процессоров размер сортируемого участка массива для каждого отдельного процессора уменьшается.

2. По числу входных данных: -0.6059. Это значит, что с ростом размеров входных данных эффективность алгоритма падает. Это можно объяснить тем, что при алгоритм предполагает многократный обмен массивами данных, а это значит, что при увеличении размера задачи накладные расходы на обмен данными между процессорами тоже сильно возрастает.

3. По двум направлениям: 0.0386. Это значит, что с ростом числа процессоров и размерами входных данных эффективность все же возрастает, но скорость не слишком велика.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T14:42:21Z

Ashabokov 415: /* Математическое описание алгоритма */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пусть для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, а правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>. <ref> https://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка </ref>

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости:

1. По числу процессоров: 1.0581. Это значит, что с увеличением количества задействованных процессоров эффективность увеличивается. Такое поведение можно объяснить тем, что при увеличении числа процессоров размер сортируемого участка массива для каждого отдельного процессора уменьшается.

2. По числу входных данных: -0.6059. Это значит, что с ростом размеров входных данных эффективность алгоритма падает. Это можно объяснить тем, что при алгоритм предполагает многократный обмен массивами данных, а это значит, что при увеличении размера задачи накладные расходы на обмен данными между процессорами тоже сильно возрастает.

3. По двум направлениям: 0.0386. Это значит, что с ростом числа процессоров и размерами входных данных эффективность все же возрастает, но скорость не слишком велика.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T14:38:48Z

Ashabokov 415: /* Математическое описание алгоритма */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пусть для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>. <ref> https://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка </ref>

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости:

1. По числу процессоров: 1.0581. Это значит, что с увеличением количества задействованных процессоров эффективность увеличивается. Такое поведение можно объяснить тем, что при увеличении числа процессоров размер сортируемого участка массива для каждого отдельного процессора уменьшается.

2. По числу входных данных: -0.6059. Это значит, что с ростом размеров входных данных эффективность алгоритма падает. Это можно объяснить тем, что при алгоритм предполагает многократный обмен массивами данных, а это значит, что при увеличении размера задачи накладные расходы на обмен данными между процессорами тоже сильно возрастает.

3. По двум направлениям: 0.0386. Это значит, что с ростом числа процессоров и размерами входных данных эффективность все же возрастает, но скорость не слишком велика.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T11:46:08Z

Ashabokov 415: /* Масштабируемость алгоритма и его реализация */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пость для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>. <ref> https://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка </ref>

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости:

1. По числу процессоров: 1.0581. Это значит, что с увеличением количества задействованных процессоров эффективность увеличивается. Такое поведение можно объяснить тем, что при увеличении числа процессоров размер сортируемого участка массива для каждого отдельного процессора уменьшается.

2. По числу входных данных: -0.6059. Это значит, что с ростом размеров входных данных эффективность алгоритма падает. Это можно объяснить тем, что при алгоритм предполагает многократный обмен массивами данных, а это значит, что при увеличении размера задачи накладные расходы на обмен данными между процессорами тоже сильно возрастает.

3. По двум направлениям: 0.0386. Это значит, что с ростом числа процессоров и размерами входных данных эффективность все же возрастает, но скорость не слишком велика.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T06:41:23Z

Ashabokov 415: /* Последовательная сложность алгоритма */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пость для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>. <ref> https://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка </ref>

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T06:39:27Z

Ashabokov 415: /* Программная реализация алгоритма */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пость для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>.

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T06:36:33Z

Ashabokov 415: /* Свойства и структура алгоритмов */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пость для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>.

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

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

== Программная реализация алгоритма ==

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости.

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T06:35:25Z

Ashabokov 415: /* Существующие реализации алгоритма */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пость для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>.

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

== Программная реализация алгоритма ==

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости.

=== Существующие реализации алгоритма ===

Реализация алгоритма быстрой сортировки имеется во многих стандартных библиотеках. Например, для языков программирования C и C++ этот алгоритм можно найти в стандартных библиотеках stdlib.h и cstdlib соответственно. В языке программирования Python имеется встроенная функция sorted(). Также реализацию этого алгоритма можно найти в пакете LAPACK DLASRT.

== Литература ==
<references />

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

2019-12-02T03:03:05Z

Ashabokov 415: /* Масштабируемость алгоритма и его реализация */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пость для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>.

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

== Программная реализация алгоритма ==

=== Масштабируемость алгоритма и его реализация ===
Проведём исследование масштабируемости параллельной реализации алгоритма быстрой сортировки согласно [[Scalability methodology|методике]]. Исследование проводится для числа процессоров [8 : 128] с шагом 8.

[[file:User ashabokov 415 eff.png|thumb|center|700px|Рисунок 4. Изменение эффективности в зависимости от числа процессоров и входных данных.]]

Далее построим оценку масштабируемости.

=== Существующие реализации алгоритма ===

== Литература ==
<references />

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

2019-11-30T22:45:09Z

Ashabokov 415: /* Свойства и структура алгоритмов */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пость для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>.

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

== Программная реализация алгоритма ==

=== Масштабируемость алгоритма и его реализация ===

=== Существующие реализации алгоритма ===

== Литература ==
<references />

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

2019-11-30T22:42:08Z

Ashabokov 415: /* Информационный граф */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пость для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>.

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Gr 1.png|thumb|center|700px|Рисунок 1. Итерация 1.]]
[[file:Gr 2.png|thumb|center|700px|Рисунок 2. Итерация 2.]]
[[file:Gr 3.png|thumb|center|700px|Рисунок 3. Итерация 3.]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

== Литература ==
<references />

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

2019-11-30T22:36:39Z

Ashabokov 415: /* Информационный граф */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пость для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>.

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

[[file:Scalability vector scalar mult.png|thumb|center|100px|Рисунок 1. ]]

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

== Литература ==
<references />

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

2019-11-30T22:34:12Z

Ashabokov 415: /* Информационный граф */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пость для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>.

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

== Литература ==
<references />

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

2019-11-30T22:02:50Z

Ashabokov 415: /* Свойства и структура алгоритмов */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пость для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>.

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===
Так как для проведения вычислений задействовано <math> p = 2^N </math> процессоров, можно воспользоваться следующим алгоритмом распределения данных между процессорами. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д.

Для наглядности приведем пример: пусть <math> p = 2^3 = 8 </math>. Ниже приведены графы, иллюстрирующие распределение данных на каждой итерации.

=== Ресурс параллелизма алгоритма ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Подробное описание метода распределения данных между вычислительными узлами можно найти в разделе 1.7. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

== Литература ==
<references />

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

2019-11-30T21:49:53Z

Ashabokov 415: /* Информационный граф */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пость для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>.

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===

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

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

== Литература ==
<references />

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

2019-11-30T21:45:56Z

Ashabokov 415: /* Последовательная сложность алгоритма */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

Быстрая сортировка, сортировка Хоара — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math> O (n \log n) </math> обменов при упорядочении <math> n </math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Фактически данный алгоритм является улучшением алгоритма сортировки прямого обмена (см. ниже).

=== Математическое описание алгоритма ===
Алгоритм состоит из трех основных шагов:

1. Выбрать опорный элемент (см. ниже). Пусть это будет элемент <math> a' </math>.

2. Используя операции сравнения элементов массива с опорным и перестановки элементов массива, привести исходный массив к виду: <math> a_1 ... a_m a' a_{m+2} ... a_n </math>, где <math> a_j < a', j = 1 ... m </math>, <math> a_i \geq a', i = (m+1) ... n </math>, где <math> n </math> — длина массива.

3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_n </math>.

Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 2. Для этого часто используют так называемое разбиение Хоара <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref>. Суть данного метода заключается в следующем: выбираются два указателя, указывающие на первый и последний элементы массива соответственно, пость для наглядности это будут <math> i = 1 </math> и <math> j = n </math>. Далее начинаем сдвигать левый указатель вправо, в правый — влево до тех пор, пока выполнены условия: <math> a_i < a', a_j \geq a', i < j </math>, где <math> a' </math> — опорный элемент. Как только найдутся такие <math> i, j </math>, что <math> a_i \geq a', a_j < a' </math> и <math> i < j </math>, производим перестановку этих двух элементов. Продолжаем этот процесс до тех пор, пока выполнено <math> i < j </math>.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром данного алгоритма являются операции сравнения и перестановки <math> i</math>-ого и <math>j</math>-ого элементов массива на каждой итерации рекурсивного алгоритма.

Сложность операции разделения массива на два подмассива (сравнение и перестановка элементов массива относительно опорного элемента) занимет время <math> O (log_2 n) </math>. <ref> https://ru.wikipedia.org/wiki/Быстрая_сортировка </ref>

=== Макроструктура алгоритма ===
Как и написано выше в разделе "Вычислительное ядро алгоритма", основную часть данного метода сортировки составляет операция разделения массива относительно опорного элемента, которая в свою очередь состоит из операций сравнения и перестановки.

=== Схема реализации последовательного алгоритма ===
1. Случайным образом выбрать опорный элемент массива.

2. Сравнить все элементы сортируемого массива с опорным и разделить исходный массив на два подмассива: с элементами меньше опорного и с элементами большие (или равные) опорного.

3. Рекурсивно повторить алгоритм для получившихся подмассивов.

Случайный выбор опорного элемента считается наиболее эффективным, так как при фиксировании позиции опорного элемента (например, в качестве опорного всегда берется элемент, стоящий на первой позиции) может привести к существенному снижению эффективности для массивов определенного вида из-за неравномерного распределения элементов в получившихся подмассивах. Также в качестве опорного элемента можно выбирать медиану массива, но считается, что вычисление медианы на каждой итерации рекурсивного алгоритма — слишком затратная операция.

=== Последовательная сложность алгоритма ===
Последовательная сложность данного алгоритма зависит от глубины рекурсии, что в свою очередь зависит от того, насколько удачно были выбраны опорные элементы на каждом витке рекурсии. Рассмотрим несколько возможных случаев.

1. В наилучшем случае выбор опорного элемента на каждом витке рекурсии происходит таким образом, что в результате разбиения исходного массива образуются подмассивы одинаковой длины (с точностью до одного элемента). В таком случае глубина рекурсии составит <math> log_2 n </math>, следовательно, общая сложность алгоритма равна <math> O(n log_2 n) </math>.

2. В наихудшем случае каждое разбиение приводит к образованию подмассивов длины <math> 1 </math> и <math> n - 1</math> соответственно. Общая сложность алгоритма в таком случае равна <math> O(n^2) </math>.

=== Информационный граф ===

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

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает выбор разделяющего элемента случайным образом, построение последовательностей специального вида не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами. Это значит, что эффективность алгоритма не зависит от вида входной последовательности.

'''Выходные данные:''' последовательность чисел в отсортированном виде.

== Литература ==
<references />

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

2019-11-30T01:22:13Z

Ashabokov 415: /* Вычислительное ядро алгоритма */

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

2019-11-30T01:21:43Z

Ashabokov 415: /* Макроструктура алгоритма */

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

2019-11-30T01:15:50Z

Ashabokov 415: /* Свойства и структура алгоритмов */

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

2019-11-29T23:53:25Z

Ashabokov 415: /* Свойства и структура алгоритмов */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===

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

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' любая числовая последовательность произвольной конечной длины. Так как параллельный алгоритм предполагает поиск разделяющего элемента случайным образом, построение последовательностей специальных видов не приводит к увеличению вероятности неравномерного распределения данных между вычислительными узлами.
'''Выходные данные:''' последовательность чисел в отсортированном виде.

== Литература ==
<references />

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

2019-10-20T23:26:42Z

Ashabokov 415: /* Общее описание алгоритма https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia */

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй — большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

== Литература ==
<references />

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

2019-10-20T23:26:07Z

Ashabokov 415: Новая страница: «'''Алгоритм быстрой сортировки''' == Свойства и структура алгоритмов == === Общее описание а…»

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

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

=== Общее описание алгоритма <ref> https://en.wikipedia.org/wiki/Quicksort — From Wikipedia, the free encyclopedia </ref> ===
Основной идеей данного алгоритма является разбиение всего массива данных на блоки меньшего размера таким образом, что между соответствующими блоками после разбиения можно установить отношение упорядоченности. Сортировка производится следующим образом: выбирается некоторым образом ведущий элемент, после чего происходит разделение исходного массива данных на два блока относительно ведущего элемента: в первый блок помещаются элементы, меньшие ведущего, а во второй --- большие ведущего. Таким образом, можно утверждать, что наибольший элемент первого блока меньше наименьшего элемента второго блока. Это означает, что повторив эту операцию для каждого из блоков отдельно некоторое количество раз и объединив результаты, получим массив с исходными данными в отсортированном виде. Из описания становится очевидно, что данный алгоритм можно легко обобщить для параллельной вычислительной системы с количеством процессоров <math>p = 2^n</math>. Для этого алгоритм необходимо лишь дополнить методом выбора процессоров, между которыми будут происходить обмены данными на i-ом шаге. Распределим произвольным образом данные между процессорами, далее выбираем некоторым образом ведущий элемент и рассылаем его всем процессорам системы. Т.к. топология системы имеет вид n-мерного куба, номер каждого процессора имеет двоичное представление длины <math>n</math>, следовательно, можно ввести правило: на каждом процессоре происходит сравнение имеющегося блока данных с текущим ведущим элементом, после чего элементы меньше ведущего отправляются от процессора с номером <math>n_1</math> процессору номер <math>n_2</math>, где <math>n_1</math> отличается от <math>n_2</math> только в n-том разряде двоичного представления, в двоичном представлении числа <math>n_1</math> на n-той позиции стоит 1, а <math>n_2</math> — 0. Таким образом, после данной операции все данные будут разделены между процессорами, образующими n-1-мерные кубы таким образом, что элемент блока данных любого процессора из первого куба больше любого элемента блока данных процессора из второго куба. Повторив аналогичные действия для каждого из n-1-мерных кубов, получим 4 n-2-мерных куба и т.д. Последним этапом работы алгоритма является объединение разрозненных блоков отсортированных данных в единый массив в правильном порядке. Порядок объединения не трудно восстановить исходя из двоичных представлений номеров процессоров.

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

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

<math>\sum_{i=1}^{n} i = n(n+1)/2 ≈ \log^2 p </math> <ref> http://ssd.sscc.ru/ru — Supercomputer Software Department </ref>,

где <math> p </math> — количество задействованных процессоров.

== Литература ==
<references />