Участник:Inna Park/Сортировка Шелла: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(Новая страница: «== Свойства и структура алгоритмов == === Общее описание алгоритма === Стандартная версия ал…»)
 
 
Строка 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> — номер соответствующей итерации.
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===

Текущая версия на 03:25, 21 октября 2019

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

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

Стандартная версия алгоритма Шелла [1] фактически представляет из себя модификацию алгоритма сортировки вставками: если в алгоритме сортировки вставками сравнивались элементы с шагом 1, то в алгоритме Шелла предлагается сравнивать элементы, стоящие на некотором расстоянии [math] d \gt 1 [/math], причем с увеличением номера итерации происходит уменьшение параметра. Это приводит к приросту эффективности в некоторых случаях в сравнении с сортировкой вставками.

Параллельный аналог метода [2]:

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

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

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

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

Важным критерием эффективности любого параллельного алгоритма является трудоемкость его выполнения. Введем следующие обозначения: [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 \lt p [/math] эффективность алгоритма Шелла выше эффективности алгоритма простой чет-нечетной перестановки.

2 Литература

  1. https://ru.wikipedia.org/wiki/Сортировка_Шелла — From Wikipedia, the free encyclopedia
  2. Kumar et al. (2003)