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

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

2019-12-02T15:08:42Z

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

← Предыдущая версия		Версия от 15:08, 2 декабря 2019
Строка 96:		Строка 96:
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

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

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

2019-12-02T15:08:10Z

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

← Предыдущая версия		Версия от 15:08, 2 декабря 2019
Строка 96:		Строка 96:
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

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

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

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

2019-12-02T14:53:56Z

Информационный граф

← Предыдущая версия		Версия от 14:53, 2 декабря 2019
Строка 45:		Строка 45:

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

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

2019-12-02T14:53:29Z

Информационный граф

← Предыдущая версия		Версия от 14:53, 2 декабря 2019
Строка 45:		Строка 45:

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

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

2019-12-02T14:48:37Z

Схема реализации последовательного алгоритма

← Предыдущая версия		Версия от 14:48, 2 декабря 2019
Строка 31:		Строка 31:
	1. Случайным образом выбрать опорный элемент массива.		1. Случайным образом выбрать опорный элемент массива.

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

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

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

2019-12-02T14:47:41Z

Схема реализации последовательного алгоритма

← Предыдущая версия		Версия от 14:47, 2 декабря 2019
Строка 31:		Строка 31:
	1. Случайным образом выбрать опорный элемент массива.		1. Случайным образом выбрать опорный элемент массива.

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

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

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

2019-12-02T14:47:08Z

Схема реализации последовательного алгоритма

← Предыдущая версия		Версия от 14:47, 2 декабря 2019
Строка 31:		Строка 31:
	1. Случайным образом выбрать опорный элемент массива.		1. Случайным образом выбрать опорный элемент массива.

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

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

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

2019-12-02T14:44:14Z

Макроструктура алгоритма

← Предыдущая версия		Версия от 14:44, 2 декабря 2019
Строка 26:		Строка 26:

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

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

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

2019-12-02T14:42:21Z

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

← Предыдущая версия		Версия от 14:42, 2 декабря 2019
Строка 18:		Строка 18:
	3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_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>.		Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 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>.

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===

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

2019-12-02T14:38:48Z

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

← Предыдущая версия		Версия от 14:38, 2 декабря 2019
Строка 18:		Строка 18:
	3. Рекурсивно применить алгоритм к каждому из массивов: <math> a_1 ... a_m </math> и <math> a_{m+1} ... a_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>.		Рассмотрим подробнее метод сравнения и перестановки данных в массиве, применяющийся на шаге 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>.

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===