Участник:Inna Park/Сортировка Шелла

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ T = (n/p)log(n/p)+(2n/p)log p + L(2n/p) }[/math].

При [math]\displaystyle{ L \lt p }[/math] эффективность алгоритма Шелла выше эффективности алгоритма простой чет-нечетной перестановки.