Участник:ElaginMD/Сортировка Шелла: различия между версиями
ElaginMD (обсуждение | вклад) |
ElaginMD (обсуждение | вклад) |
||
| Строка 47: | Строка 47: | ||
| Текст ячейки || <math>Θ({n^2})</math> || Д.Шелл | | Текст ячейки || <math>Θ({n^2})</math> || Д.Шелл | ||
|- | |- | ||
| Текст ячейки || <math>Θ( | | Текст ячейки || <math>Θ(n^{3/2})</math> || Т.Хиббард | ||
|- | |- | ||
| Текст ячейки || <math>Θ({n^3/2})</math> || В.Пратт | | Текст ячейки || <math>Θ({n^3/2})</math> || В.Пратт | ||
Версия от 18:23, 2 ноября 2025
Свойства и структура алгоритмов
Общее описание алгоритма
Сортировка Шелла, более известная как «сортировка с убывающим шагом». Данная сортировка оптимизация сортировки вставками, которая позволяет обмениваться элементами, находящимися далеко друг от друга. Идея состоит в том, чтобы расположить список элементов таким образом, чтобы, начиная с любого места, беря каждый [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] оставляет очень мало работы для этого последнего прохода.[1]
Проще говоря, это означает, что если у нас есть массив из [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]. На каждом шаге для упорядочивания полученных наборов элементов, используется метод сортировки вставками.[2].
Вычислительное ядро алгоритма
Вычислительным ядром алгоритма сортировки Шелла является сортировка вставками. На каждом шаге алгоритм разбивает исходный массив на несколько подмассивов с определенным интервалом, и каждый из этих подмассивов сортируется методом вставок.
Макроструктура алгоритма
В реализации данного алгоритма в качестве основного вычислительного ядра используется алгоритм сортировки вставками.
Сортировка вставками
Сортировка вставками, также известен как insertion sort - алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.[3]
Принцип работы алгоритма заключается в том, что на каждой итерации алгоритм берёт очередной элемент и сравнивает его со всеми элементами уже отсортированной части, находя подходящую позицию для вставки. Когда такая позиция находится, элементы, большие вставляемого, сдвигаются на одну позицию вправо, освобождая место для вставки текущего элемента. Этот процесс повторяется для всех элементов массива, начиная со второго и до последнего. Вычислительная сложность - [math]\displaystyle{ O({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}) }[/math] | Д.Шелл |
| Текст ячейки | [math]\displaystyle{ Θ(n^{3/2}) }[/math] | Т.Хиббард |
| Текст ячейки | [math]\displaystyle{ Θ({n^3/2}) }[/math] | В.Пратт |
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
На вход алгоритму подается одномерный массив произвольных сравниваемых элементов. Массив может быть произвольной длины и содержать элементы любого типа данных, для которых определена операция сравнения. Элементы массива могут быть как уникальными, так и содержать повторяющиеся элементы.
На выходе алгоритм возвращает одномерный массив той же длины, что и входной, содержащий те же элементы, но упорядоченные по возрастанию или убыванию в зависимости от реализации операции сравнения.
Литература
- ↑ Скворцова, Л. А. Структуры и алгоритмы обработки данных : учебно-методическое пособие / Л. А. Скворцова, К. В. Гусев, С. М. Трушин. — Москва : РТУ МИРЭА, 2021. — 235 с.
- ↑ Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Вильямс, 2001 — 384 с.
- ↑ Кнут Д. Э. 5.2 Внутренняя сортировка // Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с.