|
|
| (не показано 36 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| == Свойства и структура алгоритмов ==
| |
| === Общее описание алгоритма ===
| |
| '''Сортировка Шелла''', более известная как «сортировка с убывающим шагом». Алгоритм выполняет несколько проходов по списку, и каждый раз сортирует несколько наборов одинакового размера, используя сортировку вставкой. Размер сортируемого набора увеличивается с каждым проходом по списку, пока он не будет состоять из всего списка. Это позволяет сортировке вставкой выполнять каждую итерацию практически в лучшем случае со сложностью, приближающейся к <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>
| |
| На первом шаге алгоритма происходит упорядочивание элементов <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>.
| |
| === Вычислительное ядро алгоритма ===
| |
| === Ресурс параллелизма алгоритма ===
| |
| === Входные и выходные данные алгоритма ===
| |
| == Литература ==
| |