Участник:ElaginMD
Свойства и структура алгоритмов
Общее описание алгоритма
Сортировка Шелла[1], более известная как «сортировка с убывающим шагом». Алгоритм выполняет несколько проходов по списку, и каждый раз сортирует несколько наборов одинакового размера, используя сортировку вставкой. Размер сортируемого набора увеличивается с каждым проходом по списку, пока он не будет состоять из всего списка. Это позволяет сортировке вставкой выполнять каждую итерацию практически в лучшем случае со сложностью, приближающейся к [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]}.
На первом шаге алгоритма[2] происходит упорядочивание элементов [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].