Метод сортировки шелла кратко

Обновлено: 28.06.2024

Сортировка Шелла была названа в честь ее изобретателя – Дональда Шелла, который опубликовал этот алгоритм в 1959 году. Общая идея сортировки Шелла состоит в сравнении на начальных стадиях сортировки пар значений, расположенных достаточно далеко друг от друга в упорядочиваемом наборе данных. Такая модификация метода сортировки позволяет быстро переставлять далекие неупорядоченные пары значений ( сортировка таких пар обычно требует большого количества перестановок, если используется сравнение только соседних элементов).

Общая схема метода состоит в следующем.

Шаг 1. Происходит упорядочивание элементов n/2 пар (x_i,x_n/2+i) для 1 .

Шаг 2. Упорядочиваются элементы в n/4 группах из четырех элементов (x_i,x_n/4+i,x_n/2+i,x_3n/4+i) для 1 .

Шаг 3. Упорядочиваются элементы уже в n/4 группах из восьми элементов и т.д.

На последнем шаге упорядочиваются элементы сразу во всем массиве x₁,x₂. x_n . На каждом шаге для упорядочивания элементов в группах используется метод сортировки вставками ( рис. 42.2).

В настоящее время неизвестна последовательность h_i,h_i-1,h_i-2. h₁ ,, оптимальность которой доказана. Для достаточно больших массивов рекомендуемой считается такая последовательность, что h_i+1=3h_i+1 , а h₁=1 . Начинается процесс с h_m , что h_m>[n/9] . Иногда значение h вычисляют проще: h_i+1=h_i/2,h₁=1,h_m=n/2 . Это упрощенное вычисление h и будем использовать далее.

Метод, предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой по месту.

Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места. Среднее время для сортировки Шелла равняется O(n 1.25 ) , для худшего случая оценкой является O(n 1.5 ) .

Быстрая сортировка Хоара

Метод быстрой сортировки был впервые описан Ч.А.Р. Хоаром в 1962 году. Быстрая сортировка – это общее название ряда алгоритмов, которые отражают различные подходы к получению критичного параметра, влияющего на производительность метода.

При общем рассмотрении алгоритма быстрой сортировки, отметим, что этот метод основывается на последовательном разделении сортируемого набора данных на блоки меньшего размера таким образом, что между значениями разных блоков обеспечивается отношение упорядоченности (для любой пары блоков все значения одного из этих блоков не превышают значений другого блока).

Опорным (ведущим) элементом называется некоторый элемент массива, который выбирается определенный образом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана , но без дополнительных сведений о сортируемых данных ее обычно невозможно получить. Необходимо выбирать постоянно один и тот же элемент (например, средний или последний по положению) или выбирать элемент со случайно выбранным индексом.

Алгоритм быстрой сортировки Хоара

Пусть дан массив x[n] размерности n .

Шаг 1. Выбирается опорный элемент массива.

Шаг 2. Массив разбивается на два – левый и правый – относительно опорного элемента. Реорганизуем массив таким образом, чтобы все элементы, меньшие опорного элемента, оказались слева от него, а все элементы, большие опорного – справа от него.

Шаг 3. Далее повторяется шаг 2 для каждого из двух вновь образованных массивов. Каждый раз при повторении преобразования очередная часть массива разбивается на два меньших и т. д., пока не получится массив из двух элементов ( рис. 42.3).

Быстрая сортировка стала популярной прежде всего потому, что ее нетрудно реализовать, она хорошо работает на различных видах входных данных и во многих случаях требует меньше затрат ресурсов по сравнению с другими методами сортировки.

Выберем в качестве опорного элемент, расположенный на средней позиции.

Эффективность быстрой сортировки в значительной степени определяется правильностью выбора опорных (ведущих) элементов при формировании блоков. В худшем случае трудоемкость метода имеет ту же сложность, что и пузырьковая сортировка , то есть порядка O(n 2 ) . При оптимальном выборе ведущих элементов, когда разделение каждого блока происходит на равные по размеру части, трудоемкость алгоритма совпадает с быстродействием наиболее эффективных способов сортировки, то есть порядка O(n log n) . В среднем случае количество операций, выполняемых алгоритмом быстрой сортировки, определяется выражением T(n) = O(1.4n log n)

Быстрая сортировка является наиболее эффективным алгоритмом из всех известных методов сортировки, но все усовершенствованные методы имеют один общий недостаток – невысокую скорость работы при малых значениях n .

Рекурсивная реализация быстрой сортировки позволяет устранить этот недостаток путем включения прямого метода сортировки для частей массива с небольшим количеством элементов. Анализ вычислительной сложности таких алгоритмов показывает, что если подмассив имеет девять или менее элементов, то целесообразно использовать прямой метод (сортировку простыми вставками).

Сортировка Шелла (англ. Shellsort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками.

Содержание

Каждый проход в алгоритме характеризуется смещением [math]h_i[/math] , таким, что сортируются элементы отстающие друг от друга на [math]h_i[/math] позиций. Шелл предлагал использовать [math]h_t = N/2[/math] , [math]h_ = h_t/2[/math] , [math]\ldots[/math] , [math]h_0 = 1[/math] . Возможны и другие смещения, но [math]h_0 = 1[/math] всегда.

Начало.
Шаг 0. [math]i = t[/math] .
Шаг 1. Разобьем массив на списки элементов, отстающих друг от друга на [math]h_i[/math] . Таких списков будет [math]h_i[/math] .
Шаг 2. Отсортируем элементы каждого списка сортировкой вставками.
Шаг 3. Объединим списки обратно в массив. Уменьшим [math]i[/math] . Если [math]i[/math] неотрицательно — вернемся к шагу 1
Конец.

Возьмем массив [math]A= \<[/math] 56, 43, 12, 78, 42, 93, 16, 55 [math]\> [/math] и смещения предложенные Шеллом.

Понятно, что сложность алгоритма зависит от оптимальности выбора набора [math]h_i[/math] . Массив, где для любого [math]i[/math] верно [math] a_i \leqslant a_[/math] , назовем [math]h[/math] упорядоченным.

Среднее число инверсий в [math]h[/math] упорядоченной перестановке множества [math]\<[/math] 1, 2, [math]\ldots[/math] , [math]n \>[/math] равно [math] f(n,h) = \dfracq!q!>(\binomq(q+1) + \binom(q+1)-1/2\binomq) [/math] , где [math]q = \frac [/math] и [math] r = n\,\bmod\,h [/math]

Следующая лемма является следствием теоремы выше.

Если последовательность смещений [math]h_, \ldots , h_1, h_0[/math] , удовлетворяют условию [math] h_\,\bmod\,h_s = 0[/math] при [math]t-1\gt s\geqslant0[/math] , то среднее число операций равно [math]D = \sum_^<> (r_sf(q_s+1,h_/h_s) + (h_s - r_s)f(q_s,h_/h_s))[/math] , где [math]r_s=N\,\bmod\,h_s[/math] , [math]q_s = \frac[/math] , [math] h_t = Nh_[/math] , а функция [math]f[/math] определяется формулой из теоремы.

Доказательство данных теоремы и леммы изложено в книге, предложенной к прочтению.

В первом приближении функция [math]f(n,h)[/math] равна [math] (\sqrt<\pi>/8)n^h^[/math] . Следовательно [math]D[/math] для двух проходов будет примерно пропорционально [math]2N^2/h+\sqrt<\pi N^3h>[/math] . Поэтому наилучшее значение [math]h[/math] равно приблизительно [math]\sqrt[3]> \approx 1.72\sqrt[3][/math] , при таком выборе [math]h[/math] среднее время сортировки пропорционально [math]N^[/math] .

Таким образом, применяя метод Шелла и используя всего 2 прохода, можно сократить время по сравнению с методом простых вставок с [math]O(N^2)[/math] до [math]O(N^)[/math] .

Используя приведенные выше формулы, порог [math]N^[/math] преодолеть невозможно, но если убрать ограничение [math] h_\,\bmod\,h_s = 0[/math] его можно преодолеть.

Если [math]h_s=2^-1[/math] при [math]0 \leqslant s \lt t = \left \lfloor \ln N \right \rfloor[/math] , то время сортировки есть [math]O(N^)[/math] .

Важно, что эта теорема дает оценку времени выполнения алгоритма в худшем случае.

Дальнейшее улучшение было получено Волганом Праттом. Если все смещения при сортировке выбираются из множества чисел вида [math]2^p3^q[/math] , меньших [math]N[/math] , то время выполнения алгоритма будет порядка [math]O(N\log^2)[/math] .

Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.

O(n log 2 n)

зависит от выбранных шагов

О(n) всего, O(1) дополнительно

Пример

Пусть дан список и выполняется его сортировка методом Шелла, а в качестве значений выбраны .

На первом шаге сортируются подсписки , составленные из всех элементов , различающихся на 5 позиций, то есть подсписки = (32, 66, 40)" />
, = (95, 35, 43)" />
, = (16, 19, 93)" />
, = (82, 75, 68)" />
, = (24, 54)" />
.

В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

Сортировка Шелла

В этом уроке будет рассмотрена сортировка Шелла. Мы приведем алгоритм, а также его реализацию на языке программирования Си с подробными комментариями.

Этот метод сортировки Д. Шелл предложил в 1959 г. Он использует минимум памяти и показывает высокие скорости при сортировке. По сути в методе Шелла применяются сравнения и перестановки элементов аналогичные методу вставок, но при этом порядок сравниваемых элементов совершенно другой.

Идея сортировки методом Шелла состоит в том, чтобы сортировать элементы отстоящие друг от друга на некотором расстоянии step. Затем сортировка повторяется при меньших значениях step, и в конце процесс сортировки Шелла завершается при step = 1 (а именно обычной сортировкой вставками).

До сих пор продолжает обсуждаться вопрос выбора шага сортировки step. Шелл предложил такую последовательность: N/2, N/4, N/8 …, где N — количество элементов в сортируемом массиве.

Сортировка Шелла требует около log₂N проходов для упорядочивания последовательности длиной N.

Читайте также: