Участник:ElaginMD: различия между версиями
ElaginMD (обсуждение | вклад) 1 -ые изменения |
ElaginMD (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== Свойства и структура алгоритмов == | == Свойства и структура алгоритмов == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
'''Сортировка Шелла''', более известная как «сортировка с убывающим шагом». Алгоритм выполняет несколько проходов по списку, и каждый раз сортирует несколько наборов одинакового размера, используя сортировку вставкой. Размер сортируемого набора увеличивается с каждым проходом по списку, пока он не будет состоять из всего списка. Это позволяет сортировке вставкой выполнять каждую итерацию практически в лучшем случае со сложностью, приближающейся к <math>O(n)</math>. | '''Сортировка Шелла'''<ref name="VVVVVV">Скворцова, Л. А. Структуры и алгоритмы обработки данных : учебно-методическое пособие / Л. А. Скворцова, К. В. Гусев, С. М. Трушин. — Москва : РТУ МИРЭА, 2021. — 235 с. </ref>, более известная как «сортировка с убывающим шагом». Алгоритм выполняет несколько проходов по списку, и каждый раз сортирует несколько наборов одинакового размера, используя сортировку вставкой. Размер сортируемого набора увеличивается с каждым проходом по списку, пока он не будет состоять из всего списка. Это позволяет сортировке вставкой выполнять каждую итерацию практически в лучшем случае со сложностью, приближающейся к <math>O(n)</math>. | ||
Элементы, содержащиеся в каждом наборе, не являются смежными, а именно, если есть <math>i</math> наборов, то набор состоит из каждого <math>i</math>-го элемента. | Элементы, содержащиеся в каждом наборе, не являются смежными, а именно, если есть <math>i</math> наборов, то набор состоит из каждого <math>i</math>-го элемента. | ||
<br><br> | <br><br> | ||
| Строка 11: | Строка 11: | ||
<math>n</math> – количество элементов в массиве {<math>{1,..,n}</math>}. | <math>n</math> – количество элементов в массиве {<math>{1,..,n}</math>}. | ||
<br> | <br> | ||
На первом шаге алгоритма происходит упорядочивание элементов <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> | На первом шаге алгоритма<ref name="VVVVV1">Ахо А.В., Хопкрофт Дж.Э., Ульман Дж.Д. Структуры данных и алгоритмы. — М.: Вильямс, 2000. — 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>. | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Ресурс параллелизма алгоритма === | === Ресурс параллелизма алгоритма === | ||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
== Литература == | == Литература == | ||
Ахо А. В., Хопкрофт Дж. Э., Ульман Дж. Д. Структуры данных и алгоритмы. — Вильямс, 2000. — 384 с. — ISBN 5-8459-0122-7. | |||
Версия от 21:36, 23 октября 2025
Свойства и структура алгоритмов
Общее описание алгоритма
Сортировка Шелла[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].
Вычислительное ядро алгоритма
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Литература
Ахо А. В., Хопкрофт Дж. Э., Ульман Дж. Д. Структуры данных и алгоритмы. — Вильямс, 2000. — 384 с. — ISBN 5-8459-0122-7.