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

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

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

Сортировка Шелла, более известная как «сортировка с убывающим шагом». Данная сортировка оптимизация сортировки вставками, которая позволяет обмениваться элементами, находящимися далеко друг от друга. Идея состоит в том, чтобы расположить список элементов таким образом, чтобы, начиная с любого места, беря каждый [math]\displaystyle{ h }[/math]-й элемент, получался отсортированный список. Такой список называется [math]\displaystyle{ h }[/math]-sorted. Его также можно представить в виде списков с чередованием, каждый из которых отсортирован по отдельности. Начало с больших значений [math]\displaystyle{ h }[/math] позволяет элементам перемещаться на большие расстояния в исходном списке, быстро уменьшая большое количество беспорядка и оставляя меньше работы для выполнения меньших шагов [math]\displaystyle{ h }[/math]-сортировки. Если список затем отсортирован по [math]\displaystyle{ k }[/math]-образному для некоторого меньшего целого числа [math]\displaystyle{ k }[/math], то список остается отсортированным по [math]\displaystyle{ h }[/math]. Финальная сортировка с [math]\displaystyle{ h = 1 }[/math] гарантирует, что список будет полностью отсортирован в конце, но разумно выбранная убывающая последовательность значений [math]\displaystyle{ h }[/math] оставляет очень мало работы для этого последнего прохода.

Проще говоря, это означает, что если у нас есть массив из [math]\displaystyle{ 1024 }[/math] чисел, наш первый разрыв [math]\displaystyle{ (h) }[/math] может быть равен [math]\displaystyle{ 512 }[/math]. Затем мы пробежимся по списку, сравнивая каждый элемент в первой половине с элементом во второй половине. Наш второй пробел [math]\displaystyle{ (k) }[/math] равен [math]\displaystyle{ 256 }[/math], который разбивает массив на четыре секции (начиная с [math]\displaystyle{ 0, 256, 512, 768 }[/math]), и мы следим за тем, чтобы первые элементы в каждой секции были отсортированы относительно друг друга, затем второй элемент в каждой секции и так далее. На практике последовательность зазоров может быть любой, но последний зазор всегда равен [math]\displaystyle{ 1 }[/math] для завершения сортировки (по сути, при обычной вставочной сортировке).

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

Описать алгоритм с использованием классической последовательности Шелла можно следующим образом.
Пусть, дан массив [math]\displaystyle{ A = [a_i, a_{i+1}, a_{i+2}, …a_n] }[/math], где [math]\displaystyle{ i }[/math] – индекс массива; [math]\displaystyle{ n }[/math] – количество элементов в массиве {[math]\displaystyle{ {1,..,n} }[/math]}.
На первом шаге алгоритма происходит упорядочивание элементов [math]\displaystyle{ n/2 }[/math] пар, [math]\displaystyle{ (a_i , a_{n/2+i}) }[/math] для [math]\displaystyle{ 1 ≤ i ≤ n/2 }[/math]. Далее на втором шаге упорядочиваются элементы в [math]\displaystyle{ n/4 }[/math] группах из четырех элементов [math]\displaystyle{ (a_i , a_{n / 4+ 1} , a_{n / 2+ 1} , a_{3 n / 4+ 1} ) }[/math] для [math]\displaystyle{ 1 ≤ i ≤ n/4 }[/math]. На третьем шаге упорядочиваются элементы уже в [math]\displaystyle{ n/4 }[/math] группах из восьми элементов и т.д. На последнем шаге упорядочиваются элементы сразу во всем массиве [math]\displaystyle{ (a_1 , a_2 ,…, a_n ) }[/math]. На каждом шаге для упорядочивания полученных наборов элементов, используется метод сортировки вставками..

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

Вычислительным ядром алгоритма сортировки Шелла является сортировка вставками. На каждом шаге алгоритм разбивает исходный массив на несколько подмассивов с определенным интервалом, и каждый из этих подмассивов сортируется методом вставок.

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

В реализации данного алгоритма в качестве основного вычислительного ядра используется алгоритм сортировки вставками.

Сортировка вставками

Сортировка вставками, также известен как insertion sort - алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.

Принцип работы алгоритма заключается в том, что на каждой итерации алгоритм берёт очередной элемент и сравнивает его со всеми элементами уже отсортированной части, находя подходящую позицию для вставки. Когда такая позиция находится, элементы, большие вставляемого, сдвигаются на одну позицию вправо, освобождая место для вставки текущего элемента. Этот процесс повторяется для всех элементов массива, начиная со второго и до последнего. Вычислительная сложность - [math]\displaystyle{ Θ({n^2}) }[/math].

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

Псевдокод

На вход алгоритму подаётся массив [math]\displaystyle{ A[1..n] }[/math], состоящий из элементов [math]\displaystyle{ A[1] }[/math],[math]\displaystyle{ A[2] }[/math],...,[math]\displaystyle{ A[n] }[/math], которые требуется отсортировать. Где [math]\displaystyle{ n }[/math] соответствует length([math]\displaystyle{ A }[/math]) - размеру исходного массива. В результате работы во входном массиве оказывается отсортированная последовательность элементов.

step = length(A) / 2
while step > 0:
   for i = step to length(A) - 1:
     j = i
     delta = j - step  
     while delta >= 0 and A[delta] > A[j]: //insert sort.
        swap(A[delta], A[j])
        j = delta
        delta = j - step
    step = step / 2

Последовательная сложность алгоритма

Последовательная сложность алгоритма зависит от выбранной последовательности в реализации алгоритма.

Последовательность ([math]\displaystyle{ k }[/math]>=1)	Сложность	Автор
[math]\displaystyle{ N/2^k }[/math]	[math]\displaystyle{ Θ({n^2}) }[/math]	Д.Шелл
[math]\displaystyle{ 2^k-1 }[/math]	[math]\displaystyle{ Θ(n^{3/2}) }[/math]	Т.Хиббард
Последовательные цифры формы [math]\displaystyle{ 2^p3^q }[/math](3-гладкие числа)	[math]\displaystyle{ Θ(n*log^2(n)) }[/math]	В.Пратт

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

Рис.1. Информационный граф.

Граф иллюстрирует работу алгоритма пошагово, таким образом легко найти ресурс параллелизма в сортировке. Процесс поэтапной сортировки вставками для каждого из изолированных подмассивов обрамлен рамкой. В блоке видно, как с помощью инкрементирования [math]\displaystyle{ i }[/math] задается начальный элемент подмассива, а затем с помощью шага [math]\displaystyle{ gap }[/math] определяются последующие элементы.

Ресурс параллелизма алгоритма

Из описания структуры алгоритма Шелла можно заметить, что данный метод поддается распараллеливанию. Ключевой ресурс параллельной обработки заключается в возможности независимой сортировки подмассивов, формируемых на каждом шаге алгоритма. При использовании больших значений шага [math]\displaystyle{ gap }[/math] образуются многочисленные изолированные (независимые друг от друга подмассивы) последовательности элементов, которые могут обрабатываться одновременно различными вычислительными процессами.
Важной особенностью параллельной работы алгоритма является динамическое изменение количества используемых нитей(процессов). На начальных стадиях сортировки, когда используются наибольшие значения [math]\displaystyle{ gap }[/math], количество независимых подмассивов достигает максимума, что позволяет эффективно задействовать процессы системы. Однако по мере уменьшения шага параллельные возможности алгоритма постепенно сокращаются, и на завершающем этапе, при [math]\displaystyle{ gap = 1 }[/math], метод полностью переходит к последовательной обработке данных, характерной для классической сортировки вставками.
Параллелизм данного алгоритма можно описать топологией в виде [math]\displaystyle{ N }[/math]-мерного гиперкуба. Где [math]\displaystyle{ N = log_2(n) }[/math],[math]\displaystyle{ n }[/math]- количество элементов массива. Вершинами куба являются индексы элементов массива.
Рассмотрим на примере неупорядоченного массива [math]\displaystyle{ A = [a_0, a_1, a_2, a_3, a_4, a_5, a_6, a_7] }[/math], где количество элементов [math]\displaystyle{ n }[/math] = [math]\displaystyle{ 8 }[/math], соответственно мерность гиперкуба [math]\displaystyle{ N = log_2(n) = 3 }[/math].

Рис.2. Топология распараллеливания сортировки Шелла в виде 3-мерного гиперкуба.

В параллельной версии алгоритма Шелла, адаптированной под топологию гиперкуба, первоначальный этап предполагает попарное сравнение и обмен данных между теми же элементами, что и в последовательном варианте [math]\displaystyle{ 0-4, 1-5, 2-6, 3-7 }[/math]. Принципиальное отличие заключается в организации коммуникаций: в структуре гиперкуба эти узлы оказываются соседними, что сокращает расстояние передачи данных до минимального значения. На следующей стадии обработки данные распределяются по двум независимым группам [math]\displaystyle{ 0-2-4-6, 1-3-5-7 }[/math], внутри которых проводится последовательность операций чет-нечетной сортировки. Финальная стадия алгоритма предполагает объединение отсортированных сегментов в результирующий массив. При этом масштабируемость метода прямо зависит от размерности гиперкуба - увеличение количества измерений позволяет достичь более высокой производительности за счет оптимизации маршрутизации данных между вычислительными узлами.

Входные и выходные данные алгоритма

На вход алгоритму подается одномерный массив произвольных сравниваемых элементов. Массив может быть произвольной длины и содержать элементы любого типа данных, для которых определена операция сравнения. Элементы массива могут быть как уникальными, так и содержать повторяющиеся элементы.
На выходе алгоритм возвращает одномерный массив той же длины, что и входной, содержащий те же элементы, но упорядоченные по возрастанию или убыванию в зависимости от реализации операции сравнения.

Программная реализация алгоритма

Результаты прогонов

Число элементов массива = [math]\displaystyle{ 100.000.000 }[/math]. Число процессов изменяется по формуле [math]\displaystyle{ p=2^n, n=0, 1, 2, …, k }[/math], где [math]\displaystyle{ k }[/math] определяется доступными ресурсами.

p	T₁ (с.)	T₂ (с.)	T₃ (с.)	Tср. (с.)
1	105.50	110.05	108.04	107.86
4	35.64	35.00	38.79	36.47
8	22.68	20.86	21.41	21.65
16	14.31	13.86	13.80	13.99
32	10.29	10.78	10.35	10.47
56	9.87	9.40	9.47	9.58

Проведенный анализ демонстрирует существенное сокращение времени, зависящего от выделенных процессов, для выполнения параллельного алгоритма сортировки данных объемом 100 миллионов элементов.
Для визуализации поведения с изменеием количества элементов массива, процессов выполняемых задачу и производительности, используем график сильной масштабируемости.

Рис.3. График сильной масштабируемости.