|
|
| (не показано 25 промежуточных версий этого же участника) |
| Строка 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>
| |
| ==== Сортировка вставками ====
| |
| '''Сортировка вставками''', также известен как insertion sort - это алгоритм сортировки, который последовательно помещает каждый элемент входного массива в его правильную позицию в уже отсортированной части массива.
| |
| '''Принцип работы алгоритма''' заключается в том, что на каждой итерации алгоритм берёт очередной элемент и сравнивает его со всеми элементами уже отсортированной части, находя подходящую позицию для вставки. Когда такая позиция находится, элементы, большие вставляемого, сдвигаются на одну позицию вправо, освобождая место для вставки текущего элемента. Этот процесс повторяется для всех элементов массива, начиная со второго и до последнего.
| |
|
| |
| ==== Псевдокод ====
| |
| На вход алгоритму подаётся массив A[1...n], состоящий из элементов <math>A[1]</math>,<math>A[2]</math>,...,<math>A[n]</math>, которые требуется отсортировать.
| |
|
| |
| === Ресурс параллелизма алгоритма ===
| |
| === Входные и выходные данные алгоритма ===
| |
| На вход алгоритму подается одномерный массив произвольных сравниваемых элементов. Массив может быть произвольной длины и содержать элементы любого типа данных, для которых определена операция сравнения. Элементы массива могут быть как уникальными, так и содержать повторяющиеся элементы.
| |
| <br>
| |
| На выходе алгоритм возвращает одномерный массив той же длины, что и входной, содержащий те же элементы, но упорядоченные по возрастанию или убыванию в зависимости от реализации операции сравнения.
| |
|
| |
| == Литература ==
| |