Сети сортировки - История изменений

Lira в 18:50, 9 мая 2019

2019-05-09T18:50:59Z

← Предыдущая версия		Версия от 18:50, 9 мая 2019
Строка 43:		Строка 43:
	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===

	Рассмотрим ряд сетей сортировки в предположении, что на каждой линии сети расположен ровно один элемент массива: <math>n ~~\eq~~ p</math>:		Рассмотрим ряд сетей сортировки в предположении, что на каждой линии сети расположен ровно один элемент массива: <math>n = p</math>:

	[[сеть сортировки простой вставкой]]		[[сеть сортировки простой вставкой]]

Lira в 18:25, 9 мая 2019

2019-05-09T18:25:53Z

← Предыдущая версия		Версия от 18:25, 9 мая 2019
Строка 34:		Строка 34:
	<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i \lt l</math>.		<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i \lt l</math>.

	Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>.		Пусть число используемых процессоров равно <math>p</math>. Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>0 \le i \le p-1</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>.
	Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>\|A_i\|=\|A_j\|, \|A_i\|=\|B_i\|</math>, для любых <math>i,j</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые ~~далее~~ параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.		Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>\|A_i\|=\|A_j\|, \|A_i\|=\|B_i\|</math>, для любых <math>i,j</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.

	==== Временные материалы (в таком виде их не следует включать) ====		==== Временные материалы (в таком виде их не следует включать) ====
Строка 42:		Строка 42:

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

			Рассмотрим ряд сетей сортировки в предположении, что на каждой линии сети расположен ровно один элемент массива: <math>n \eq p</math>:

			[[сеть сортировки простой вставкой]]

			[[сеть нечетно-четной перестановки]]

			[[сеть четно-нечетного слияния Бетчера]]

			[[сеть битонной сортировки]]

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

Lira в 18:10, 9 мая 2019

2019-05-09T18:10:23Z

← Предыдущая версия		Версия от 18:10, 9 мая 2019
Строка 2:		Строка 2:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	'''Сети сортировки''' используются для ~~параллельной сортировки~~ больших ~~объемов~~ данных. Каждая сеть сортировки задаёт		'''Сети сортировки''' используются для упорядочивания больших массивов данных с помощью многопроцессорных вычислительных систем. Использование многопроцессорных систем, в ом числе с распределенной оперативной памятью, позволяет достигнуть двух основных целей: 1) снизить время выполнения сортировки; 2) благодаря использованию систем с распределенной оперативной памятью снять ограничение на размер обрабатываемого массива, за счет использования совокупной оперативной памяти всех вычислительных узлов.
	расписание, обеспечивающее согласованную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны, с точки зрения последовательного выполнения, но обеспечивают эффективную параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, ~~известные~~ только ~~для некоторого фиксированного числа элементов~~.		Каждая сеть сортировки задаёт расписание, обеспечивающее согласованную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны, с точки зрения последовательного выполнения, но обеспечивают эффективную параллельную сортировку. Можно выделить масштабируемые сети сортировки, правила создания которых известны для произвольного числа процессоров, и немасштабируемые сети, предназначенные для выполнения только на вычислительных системах некоторых фиксированных размеров.

	К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть нечетно-четной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. ~~К немасштабируемым следует отнести ряд~~ [[оптимальные сети сортировки\| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6~~, 9~~, 10~~, 12 и 16~~ элементов<ref>Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.</ref>.		К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть нечетно-четной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. Среди немасштабируемых известны [[оптимальные сети сортировки\| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 10 элементов<ref>Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.</ref>, а так же наилучшие из известных сегодня сетей для 12 и 16 элементов.

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
Строка 33:		Строка 33:

	<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i \lt l</math>.		<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i \lt l</math>.

	~~==== Временные материалы (в таком виде их не следует включать) ====~~

	Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>.		Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>.
	Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>\|A_i\|=\|A_j\|, \|A_i\|=\|B_i\|</math>, для любых <math>i,j</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.		Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>\|A_i\|=\|A_j\|, \|A_i\|=\|B_i\|</math>, для любых <math>i,j</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.

			==== Временные материалы (в таком виде их не следует включать) ====

	Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой вычислительной сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.		Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой вычислительной сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.

Lira в 17:29, 9 мая 2019

2019-05-09T17:29:52Z

← Предыдущая версия		Версия от 17:29, 9 мая 2019
Строка 22:		Строка 22:
	Тогда, массив <math>B</math> упорядочен, если выполняется соотношение<nowiki>:</nowiki>		Тогда, массив <math>B</math> упорядочен, если выполняется соотношение<nowiki>:</nowiki>

	<math>B^i\le B^j</math> , для любых допустимых <math>i,j</math>, при <math>i<j</math>.		<math>B^i\le B^j</math> , для любых допустимых <math>i,j</math>, при <math>i \lt j</math>.

	Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Пусть элементы массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>.		Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Пусть элементы массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>.
Строка 30:		Строка 30:
	Тогда, массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki>		Тогда, массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki>

	<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k<j</math>,		<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k \lt j</math>,

	<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i<l</math>.		<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i \lt l</math>.

	==== Временные материалы (в таком виде их не следует включать) ====		==== Временные материалы (в таком виде их не следует включать) ====

	Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>.		Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>.
	Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>\|A_i\|=\|B_i\|</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.		Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>\|A_i\|=\|A_j\|, \|A_i\|=\|B_i\|</math>, для любых <math>i,j</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.

	Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой вычислительной сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.		Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой вычислительной сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.

AntonChupin в 12:18, 8 июля 2016

2016-07-08T12:18:23Z

← Предыдущая версия		Версия от 12:18, 8 июля 2016
Строка 73:		Строка 73:

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]
			[[Категория:Алгоритмы сортировки]]

ASA в 08:38, 29 июля 2015

2015-07-29T08:38:36Z

← Предыдущая версия		Версия от 08:38, 29 июля 2015
Строка 1:		Строка 1:
	== ~~Описание свойств~~ и ~~структуры~~ алгоритма ==		== Свойства и структура алгоритма ==
	=== ~~Словесное~~ описание алгоритма ===		=== Общее описание алгоритма ===

	'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт		'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт
	расписание, обеспечивающее согласованную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны, с точки зрения последовательного выполнения, но обеспечивают эффективную параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для некоторого фиксированного числа элементов.		расписание, обеспечивающее согласованную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны, с точки зрения последовательного выполнения, но обеспечивают эффективную параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для некоторого фиксированного числа элементов.

	К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть нечетно-четной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки\| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 элементов~~[1]~~.		К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть нечетно-четной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки\| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 элементов<ref>Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.</ref>.

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

	Исходные данные: одномерный массив <math>A</math>, содержащий <math>n</math> элементов, <math>\|A\|=n</math>.		Исходные данные: одномерный массив <math>A</math>, содержащий <math>n</math> элементов, <math>\|A\|=n</math>.
Строка 42:		Строка 42:

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
	=== ~~Описание схемы~~ реализации последовательного алгоритма ===		=== Макроструктура алгоритма ===
			=== Схема реализации последовательного алгоритма ===
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===
	=== Информационный граф ===		=== Информационный граф ===
	=== ~~Описание ресурса~~ параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	=== ~~Описание входных~~ и ~~выходных данных~~ ===		=== Входные и выходные данные алгоритма ===
	=== Свойства алгоритма ===		=== Свойства алгоритма ===

	== Программная реализация ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	=== ~~Описание локальности~~ данных и вычислений ===		=== Локальность данных и вычислений ===
	==== ~~Описание локальности алгоритма ====~~		==== Локальность реализации алгоритма ====
	~~==== Описание локальности~~ реализации алгоритма ====		===== Структура обращений в память и качественная оценка локальности =====
	===== ~~Описание структуры~~ обращений в память и качественная оценка локальности =====
	[[Файл:Sort01.png\|thumb\|center\|1110px\|Профиль доступа к памяти]]		[[Файл:Sort01.png\|thumb\|center\|1110px\|Профиль доступа к памяти]]

			=== Возможные способы и особенности параллельной реализации алгоритма ===
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности реализации ~~параллельного~~ алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	==== ~~Описание масштабируемости~~ алгоритма ====		==== Масштабируемость алгоритма ====
	==== ~~Описание масштабируемости~~ реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

	== Литература ==		== Литература ==
	# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.		<references />


	# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.		# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.


	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

Nebaruzdin: Добавление категории.

2015-03-28T02:04:24Z

Добавление категории.

← Предыдущая версия		Версия от 02:04, 28 марта 2015
Строка 69:		Строка 69:
	# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.		# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.
	# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.		# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.


			[[Категория:Начатые статьи]]

Lira: /* Словесное описание алгоритма */

2015-03-01T22:46:11Z

Словесное описание алгоритма

← Предыдущая версия		Версия от 22:46, 1 марта 2015
Строка 3:		Строка 3:

	'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт		'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт
	расписание, обеспечивающее ~~безконфликтную~~ параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают ~~быструю~~ параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для ~~массивов некоторых фиксированных размеров~~.		расписание, обеспечивающее согласованную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны, с точки зрения последовательного выполнения, но обеспечивают эффективную параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для некоторого фиксированного числа элементов.

	К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть ~~четно~~-~~нечетной~~ перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки\| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 ~~процессоров~~ [1].		К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть нечетно-четной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки\| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 элементов[1].

	=== Математическое описание ===		=== Математическое описание ===

Lira: /* Временные материалы (в таком виде их не следует включать) */

2015-03-01T21:49:18Z

Временные материалы (в таком виде их не следует включать)

← Предыдущая версия		Версия от 21:49, 1 марта 2015
Строка 39:		Строка 39:
	Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>\|A_i\|=\|B_i\|</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.		Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>\|A_i\|=\|B_i\|</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.

	Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.		Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой вычислительной сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.

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

Lira: /* Математическое описание */

2015-03-01T19:40:54Z

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

← Предыдущая версия		Версия от 19:40, 1 марта 2015
Строка 9:		Строка 9:
	=== Математическое описание ===		=== Математическое описание ===

	Исходные данные: одномерный массив <math>A</math> содержащий <math>n</math> элементов, <math>\|A\|=n</math>.		Исходные данные: одномерный массив <math>A</math>, содержащий <math>n</math> элементов, <math>\|A\|=n</math>.

	Вычисляемые данные: упорядоченный массив <math>B=sort(A)</math>.		Вычисляемые данные: упорядоченный массив <math>B=sort(A)</math>.
Строка 40:		Строка 40:

	Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.		Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.


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