Участник:ElaginMD

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

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

Сортировка Шелла, более известная как «сортировка с убывающим шагом». Алгоритм выполняет несколько проходов по списку, и каждый раз сортирует несколько наборов одинакового размера, используя сортировку вставкой. Размер сортируемого набора увеличивается с каждым проходом по списку, пока он не будет состоять из всего списка. Это позволяет сортировке вставкой выполнять каждую итерацию практически в лучшем случае со сложностью, приближающейся к [math]\displaystyle{ O(n) }[/math]. Элементы, содержащиеся в каждом наборе, не являются смежными, а именно, если есть [math]\displaystyle{ i }[/math] наборов, то набор состоит из каждого [math]\displaystyle{ i }[/math]-го элемента.

Например, если есть 3 набора, то первый набор будет содержать элементы, расположенные на позициях 1, 4, 7 и так далее. Второй набор будет содержать элементы, расположенные на позициях 2, 5, 8 и так далее; а третий набор будет содержать элементы, расположенные на позициях 3, 6, 9 и так далее.

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

Пусть, дан массив [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]. На каждом шаге для упорядочивания полученных наборов элементов, используется метод сортировки вставками. Как можно заметить, общее количество итераций алгоритма Шелла является равным [math]\displaystyle{ log_2(n) }[/math].

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

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

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

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