Inna Park: /* Общее описание алгоритма */

2019-10-21T00:25:48Z

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

← Предыдущая версия		Версия от 00:25, 21 октября 2019
Строка 1:		Строка 1:
	== Свойства и структура алгоритмов ==		== Свойства и структура алгоритмов ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	Стандартная версия алгоритма Шелла <ref> https://ru.wikipedia.org/wiki/Сортировка_Шелла — From Wikipedia, the free encyclopedia</ref> фактически представляет из себя модификацию алгоритма сортировки вставками: если в алгоритме сортировки вставками сравнивались элементы с шагом 1, то в алгоритме Шелла предлагается сравнивать элементы, ~~отстающие друг от друга~~ на некотором расстоянии <math> d > 1 </math>, причем с увеличением номера итерации происходит уменьшение параметра. Это приводит к приросту эффективности в некоторых случаях в сравнении с сортировкой вставками.		Стандартная версия алгоритма Шелла <ref> https://ru.wikipedia.org/wiki/Сортировка_Шелла — From Wikipedia, the free encyclopedia</ref> фактически представляет из себя модификацию алгоритма сортировки вставками: если в алгоритме сортировки вставками сравнивались элементы с шагом 1, то в алгоритме Шелла предлагается сравнивать элементы, стоящие на некотором расстоянии <math> d > 1 </math>, причем с увеличением номера итерации происходит уменьшение параметра. Это приводит к приросту эффективности в некоторых случаях в сравнении с сортировкой вставками.

	Параллельный аналог метода <ref> Kumar et al.		Параллельный аналог метода <ref> Kumar et al.
Строка 10:		Строка 10:
	2) Реализация итерация параллельного алгоритма чет-нечетной перестановки. Данный шаг выполняется до прекращения изменения сортируемого блока данных.		2) Реализация итерация параллельного алгоритма чет-нечетной перестановки. Данный шаг выполняется до прекращения изменения сортируемого блока данных.

	Алгоритм чет-нечетной перестановки представляет из себя сравнение элементов массива, стоящих на четных позициях, если <math>i</math> — четное, и нечетных, если <math>i</math> — нечетное, с соседними элементами, где <math>i</math> — номер соответствующей итерации.		Алгоритм чет-нечетной перестановки представляет из себя сравнение элементов массива, стоящих на четных позициях, если <math>i</math> — четное, и нечетных, если <math>i</math> — нечетное, с соседними элементами, где <math>i</math> — номер соответствующей итерации.

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

Inna Park: Новая страница: «== Свойства и структура алгоритмов == === Общее описание алгоритма === Стандартная версия ал…»

2019-10-21T00:24:36Z

Новая страница: «== Свойства и структура алгоритмов == === Общее описание алгоритма === Стандартная версия ал…»

Новая страница

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
Стандартная версия алгоритма Шелла <ref> https://ru.wikipedia.org/wiki/Сортировка_Шелла — From Wikipedia, the free encyclopedia</ref> фактически представляет из себя модификацию алгоритма сортировки вставками: если в алгоритме сортировки вставками сравнивались элементы с шагом 1, то в алгоритме Шелла предлагается сравнивать элементы, отстающие друг от друга на некотором расстоянии <math> d > 1 </math>, причем с увеличением номера итерации происходит уменьшение параметра. Это приводит к приросту эффективности в некоторых случаях в сравнении с сортировкой вставками.

Параллельный аналог метода <ref> Kumar et al.
(2003) </ref>:

1) <math>N</math> итераций взаимодействия соседних процессоров (соседних в смысле расположения номеров процессоров в N-мерном кубе, где <math> p = 2^N </math>, <math>p</math> — количество процессоров);

2) Реализация итерация параллельного алгоритма чет-нечетной перестановки. Данный шаг выполняется до прекращения изменения сортируемого блока данных.

Алгоритм чет-нечетной перестановки представляет из себя сравнение элементов массива, стоящих на четных позициях, если <math>i</math> — четное, и нечетных, если <math>i</math> — нечетное, с соседними элементами, где <math>i</math> — номер соответствующей итерации.

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

Важным критерием эффективности любого параллельного алгоритма является трудоемкость его выполнения. Введем следующие обозначения: <math>n</math> — количество данных, <math>p</math> — количество задействованных процессоров, <math>L</math> — количество итераций алгоритма чет-нечетной перестановки. Тогда трудоемкость параллельного алгоритма вычисляется формулой:

<math> T = (n/p)log(n/p)+(2n/p)log p + L(2n/p) </math>.

При <math> L < p </math> эффективность алгоритма Шелла выше эффективности алгоритма простой чет-нечетной перестановки.

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

Участник:Inna Park/Сортировка Шелла - История изменений

Inna Park: /* Общее описание алгоритма */

Inna Park: Новая страница: «== Свойства и структура алгоритмов == === Общее описание алгоритма === Стандартная версия ал…»