|
|
| (не показано 29 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| == Свойства и структура алгоритмов ==
| |
| === Общее описание алгоритма ===
| |
| '''Сортировка Шелла'''<ref name="VVVVVV">Скворцова, Л. А. Структуры и алгоритмы обработки данных : учебно-методическое пособие / Л. А. Скворцова, К. В. Гусев, С. М. Трушин. — Москва : РТУ МИРЭА, 2021. — 235 с. </ref>, более известная как «сортировка с убывающим шагом». Алгоритм выполняет несколько проходов по списку, и каждый раз сортирует несколько наборов одинакового размера, используя сортировку вставкой. Размер сортируемого набора увеличивается с каждым проходом по списку, пока он не будет состоять из всего списка. Это позволяет сортировке вставкой выполнять каждую итерацию практически в лучшем случае со сложностью, приближающейся к <math>O(n)</math>.
| |
| Элементы, содержащиеся в каждом наборе, не являются смежными, а именно, если есть <math>i</math> наборов, то набор состоит из каждого <math>i</math>-го элемента.
| |
| <br><br>
| |
|
| |
|
| Например, если есть 3 набора, то первый набор будет содержать элементы, расположенные на позициях 1, 4, 7 и так далее. Второй набор будет содержать элементы, расположенные на позициях 2, 5, 8 и так далее; а третий набор будет содержать элементы, расположенные на позициях 3, 6, 9 и так далее.
| |
| === Математическое описание алгоритма ===
| |
|
| |
| Пусть, дан массив <math>A = [a_i, a_{i+1}, a_{i+2}, …a_n]</math>, где <math>i</math> – индекс массива;
| |
| <math>n</math> – количество элементов в массиве {<math>{1,..,n}</math>}.
| |
| <br>
| |
| На первом шаге алгоритма<ref name="VVVVV1">Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Вильямс, 2001 — 384 с. </ref> происходит упорядочивание элементов <math>n/2</math> пар, <math>(a_i , a_{n/2+i})</math> для <math>1 ≤ i ≤ n/2</math>. Далее на втором шаге упорядочиваются элементы в <math>n/4</math> группах из четырех элементов <math>(a_i , a_{n / 4+ 1} , a_{n / 2+ 1} , a_{3 n / 4+ 1} )</math> для <math>1 ≤ i ≤ n/4</math>. На третьем шаге упорядочиваются элементы уже в <math>n/4</math> группах из восьми элементов и т.д. На последнем шаге упорядочиваются элементы сразу во всем массиве <math>(a_1 , a_2 ,…, a_n )</math>. На каждом шаге для упорядочивания полученных наборов элементов, используется метод сортировки вставками. Как можно заметить, общее количество итераций алгоритма Шелла является равным <math>log_2(n)</math>.
| |
|
| |
| === Вычислительное ядро алгоритма ===
| |
| Вычислительным ядром алгоритма сортировки Шелла является сортировка вставками. На каждом шаге алгоритм разбивает исходный массив на несколько подмассивов с определенным интервалом, и каждый из этих подмассивов сортируется методом вставок.
| |
|
| |
| === Макроструктура алгоритма ===
| |
| === Ресурс параллелизма алгоритма ===
| |
| === Входные и выходные данные алгоритма ===
| |
| На вход алгоритму подается одномерный массив произвольных сравниваемых элементов. Массив может быть произвольной длины и содержать элементы любого типа данных, для которых определена операция сравнения. Элементы массива могут быть как уникальными, так и содержать повторяющиеся элементы.
| |
| <br>
| |
| На выходе алгоритм возвращает одномерный массив той же длины, что и входной, содержащий те же элементы, но упорядоченные по возрастанию или убыванию в зависимости от реализации операции сравнения.
| |
|
| |
| == Литература ==
| |