Шеллсорт

Шеллсорт

Сортировка Шелла с пропусками 23, 10, 4, 1 в действии
Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	На ​ 2 ) (наихудшая известная последовательность разрывов в худшем случае) ( нлог О 2 n ) (наилучшая известная последовательность пробелов в худшем случае)
Лучшая производительность	O( n log n ) (большинство последовательностей с пробелами) ( нлог О 2 n ) (наиболее известная последовательность пробелов для наихудшего случая)
Средняя производительность	зависит от последовательности пробелов
Наихудшая пространственная сложность	О( n ) всего, O(1) вспомогательного
Оптимальный	Нет

Обмен парами элементов на последовательных шагах сортировки Шелл с пробелами 5, 3, 1.

Сортировка Шелла , также известная как сортировка Шелла или метод Шелла , представляет собой на месте сортировку сравнения . Ее можно рассматривать либо как обобщение сортировки обменом ( пузырьковая сортировка ), либо сортировку вставкой ( сортировка вставками ). Метод начинается с сортировки пар элементов, находящихся далеко друг от друга, а затем постепенно сокращается разрыв между сравниваемыми элементами. Начав с удаленных друг от друга элементов, он может переместить некоторые неуместные элементы в нужное положение быстрее, чем простой обмен ближайшими соседями. Дональд Шелл опубликовал первую версию такого рода в 1959 году. Время работы Shellsort во многом зависит от используемой последовательности пропусков. Для многих практических вариантов определение их временной сложности остается открытой проблемой .

Описание

Сортировка Шелл — это оптимизация сортировки вставками , позволяющая обмениваться элементами, находящимися далеко друг от друга. Идея состоит в том, чтобы упорядочить список элементов так, чтобы, начиная с любого места, при взятии каждого h -го элемента получался отсортированный список. Такой список называется h -сортированным. Его также можно рассматривать как h чередующихся списков, каждый из которых отсортирован индивидуально. Начиная с больших значений h, элементы могут перемещаться на большие расстояния в исходном списке, быстро уменьшая большой беспорядок и оставляя меньше работы для h -сортировки. выполнения меньших шагов Если затем список отсортирован по k для некоторого меньшего целого числа k , то список останется отсортированным по h . Окончательная сортировка с h = 1 гарантирует, что список будет полностью отсортирован в конце. но разумно выбранная убывающая последовательность значений h оставляет очень мало работы для этого последнего прохода.

Проще говоря, это означает, что если у нас есть массив из 1024 чисел, наш первый пробел ( h ) может быть 512. Затем мы просматриваем список, сравнивая каждый элемент в первой половине с элементом во второй половине. Наш второй пробел ( k ) равен 256, что разбивает массив на четыре секции (начиная с 0, 256, 512, 768), и мы проверяем, что первые элементы в каждой секции отсортированы относительно друг друга, а затем второй элемент в каждый раздел и так далее. На практике последовательность пробелов может быть любой, но последний пробел всегда равен 1, чтобы завершить сортировку (фактически завершая обычную сортировку вставками).

Ниже показан пример выполнения Shellsort с пробелами 5, 3 и 1.

	1 ​	aа2	aа3	a 4	aа5	6 ​	a 7	й 8-	aа9	10 ​	в 11	12 ​
Входные данные	62	83	18	53	07	17	95	86	47	69	25	28
После 5-сортировки	17	28	18	47	07	25	83	86	53	69	62	95
После 3-сортировки	17	07	18	47	28	25	69	62	53	83	86	95
После 1-сортировки	07	17	18	25	28	47	53	62	69	83	86	95

Первый проход, 5-сортировка, выполняет сортировку вставкой в ​​пяти отдельных подмассивах ( a ₁ , a ₆ , a ₁₁ ), ( a ₂ , a ₇ , a ₁₂ ), ( a ₃ , a ₈ ), ( a ₄ , a ₉ , ( 5 ₁₀ , ) ₎ . Например, он меняет подмассив ( a ₁ , a ₆ , a ₁₁ ) с (62, 17, 25) на (17, 25, 62). Следующий проход, 3-сортировка, выполняет сортировку вставкой для трех подмассивов ( a ₁ , a ₄ , a ₇ , a ₁₀ ), ( a ₂ , a ₅ , a ₈ , a ₁₁ ), ( a ₃ , a ₆ , 9 _​ , 12 ₎ . Последний проход, сортировка по 1, представляет собой обычную сортировку вставкой всего массива ( a ₁ ,..., a ₁₂ ).

Как показано в примере, подмассивы, над которыми работает Shellsort, изначально короткие; позже они длиннее, но почти заказаны. В обоих случаях сортировка вставками работает эффективно.

В отличие от сортировки вставками , сортировка Шелл не является стабильной сортировкой , поскольку вставки с пробелами перемещают одинаковые элементы друг за другом и, таким образом, теряют свой первоначальный порядок. Это адаптивный алгоритм сортировки , поскольку он выполняется быстрее, если входные данные отсортированы частично.

Псевдокод

Использование последовательности пробелов Марцина Чиуры с внутренней сортировкой вставками.

# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]  # Ciura gap sequence

# Start with the largest gap and work down to a gap of 1
# similar to insertion sort but instead of 1, gap is being used in each step
foreach (gap in gaps)
{
    # Do a gapped insertion sort for every elements in gaps
    # Each loop leaves a[0..gap-1] in gapped order
    for (i = gap; i < n; i += 1)
    {
        # save a[i] in temp and make a hole at position i
        temp = a[i]
        # shift earlier gap-sorted elements up until the correct location for a[i] is found
        for (j = i; (j >= gap) && (a[j - gap] > temp); j -= gap)
        {
            a[j] = a[j - gap]
        }
        # put temp (the original a[i]) in its correct location
        a[j] = temp
    }
}

Последовательности пробелов

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

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

ОЭИС	Общий термин ( k ≥ 1)	Бетонные зазоры	В худшем случае временная сложность	Автор и год издания
	$\left\lfloor {\frac {N}{2^{k}}}\right\rfloor$	$1,2,\ldots ,\left\lfloor {\frac {N}{4}}\right\rfloor ,\left\lfloor {\frac {N}{2}}\right\rfloor$	$\Theta \left(N^{2}\right)$ [например, когда N = 2 п ]	Шелл , 1959 год.
	$2\left\lfloor {\frac {N}{2^{k+1}}}\right\rfloor +1$	$1,3,\ldots ,\;2\left\lfloor {\frac {N}{8}}\right\rfloor +1,\;\;2\left\lfloor {\frac {N}{4}}\right\rfloor +1$	$\Theta \left(N^{\frac {3}{2}}\right)$	Фрэнк и Лазарус, 1960 г.
А000225	$2^{k}-1$	$1,3,7,15,31,63,\ldots$	$\Theta \left(N^{\frac {3}{2}}\right)$	Хиббард , 1963 год.
А083318	$2^{k}+1$, с префиксом 1	$1,3,5,9,17,33,65,\ldots$	$\Theta \left(N^{\frac {3}{2}}\right)$	Папернов и Стасевич, 1965 г.
А003586	Последовательные номера формы $2^{p}3^{q}$ ( 3-гладкие числа)	$1,2,3,4,6,8,9,12,\ldots$	$\Theta \left(N\log ^{2}N\right)$	Пратт , 1971 год.
А003462	${\frac {3^{k}-1}{2}}$, не более $\left\lceil {\frac {N}{3}}\right\rceil$	$1,4,13,40,121,\ldots$	$\Theta \left(N^{\frac {3}{2}}\right)$	Кнут , 1973 г., по мотивам Пратта , 1971 г.
А036569	${\begin{aligned}&\prod \limits _{I}a_{q},{\hbox{where}}\\a_{0}={}&3\\a_{q}={}&\min \left\{n\in \mathbb {N} \colon n\geq \left({\frac {5}{2}}\right)^{q+1},\forall p\colon 0\leq p<q\Rightarrow \gcd(a_{p},n)=1\right\}\\I={}&\left\{0\leq q<r\mid q\neq {\frac {1}{2}}\left(r^{2}+r\right)-k\right\}\\r={}&\left\lfloor {\sqrt {2k+{\sqrt {2k}}}}\right\rfloor \end{aligned}}$	$1,3,7,21,48,112,\ldots$	$O\left(N^{1+{\sqrt {\frac {8\ln \left(5/2\right)}{\ln(N)}}}}\right)$	Инчерпи и Седжвик , 1985 г., Кнут
А036562	$4^{k}+3\cdot 2^{k-1}+1$, с префиксом 1	$1,8,23,77,281,\ldots$	$O\left(N^{\frac {4}{3}}\right)$	Седжвик, 1982 год.
А033622	${\begin{cases}9\left(2^{k}-2^{\frac {k}{2}}\right)+1&k{\text{ even}},\\8\cdot 2^{k}-6\cdot 2^{(k+1)/2}+1&k{\text{ odd}}\end{cases}}$	$1,5,19,41,109,\ldots$	$O\left(N^{\frac {4}{3}}\right)$	Седжвик, 1986 год.
	$h_{k}=\max \left\{\left\lfloor {\frac {5h_{k-1}-1}{11}}\right\rfloor ,1\right\},h_{0}=N$	$1,\ldots ,\left\lfloor {\frac {5}{11}}\left\lfloor {\frac {5N-1}{11}}\right\rfloor -{\frac {1}{11}}\right\rfloor ,\left\lfloor {\frac {5N-1}{11}}\right\rfloor$	Un­known	Гоннет и Баеза-Йейтс , 1991 г.
А108870	$\left\lceil {\frac {1}{5}}\left(9\cdot \left({\frac {9}{4}}\right)^{k-1}-4\right)\right\rceil$ (или, что то же самое, $\left\lceil {\frac {\left(9/4\right)^{k}-1}{\left(9/4\right)-1}}\right\rceil$)	$1,4,9,20,46,103,\ldots$	Un­known	Токуда, 1992 г. (ошибочная цитата согласно OEIS)
А102549	Неизвестно (получено экспериментально)	$1,4,10,23,57,132,301,701$	Un­known	Чура, 2001 г.
А366726	$\left\lceil {\frac {\gamma ^{k}-1}{\gamma -1}}\right\rceil ,\gamma =2.243609061420001\ldots$	$1,4,9,20,45,102,230,516,\ldots$	Un­known	Ли, 2021 г.
	$\left\lfloor 4.0816\cdot 8.5714^{\frac {k}{2.2449}}\right\rfloor$	$1,4,10,27,72,187,488,\ldots$	Un­known	Скин, Эренборг, Яромчик, 2023 г.

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

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

Гонне и Баеза-Йейтс заметили, что сортировка Шелл в среднем проводит наименьшее количество сравнений, когда соотношение последовательных пробелов примерно равно 2,2. Вот почему их последовательность с соотношением 2,2 и последовательность Токуды с соотношением 2,25 оказываются эффективными. Однако неизвестно, почему это так. Седжвик рекомендует использовать пробелы, которые имеют низкие наибольшие общие делители или попарно взаимно просты . Пробелы с нечетными номерами, похоже, хорошо работают на практике: наблюдалось сокращение на 25% за счет исключения пробелов с четными номерами. Разрывы, которые позволяют избежать кратных 3 и 5, по-видимому, дают небольшую выгоду <10%.

Что касается среднего числа сравнений, последовательность Чиуры имеет самые известные характеристики; пропуски больше 701 не определялись, но последовательность можно расширить по рекурсивной формуле $h_{k}=\lfloor 2.25h_{k-1}\rfloor$.

Последовательность Токуды, определяемая простой формулой $h_{k}=\lceil h'_{k}\rceil$, где $h'_{k}=2.25h'_{k-1}+1$, $h'_{1}=1$, можно рекомендовать для практического применения.

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

Вычислительная сложность

Имеет место следующее свойство: после h ₂ -сортировки любого массива, отсортированного по h ₁ , массив остается h ₁ -отсортированным. Каждый массив с h ₁ -sorted и h ₂ -sorted также ( a ₁ h ₁ + a ₂ h ₂ )-отсортирован для любых неотрицательных целых чисел a ₁ и a ₂ . Таким образом, наихудшая сложность сортировки Шелла связана с проблемой Фробениуса : для заданных целых чисел h ₁ ,..., h _n с gcd = 1 число Фробениуса g ( h ₁ ,..., h _n ) является наибольшим целое число, которое не может быть представлено в виде a ₁ h ₁ + ... + a _n h _n с неотрицательным целым числом a ₁ ,..., a _n . Используя известные формулы для чисел Фробениуса, мы можем определить наихудшую сложность сортировки Шелла для нескольких классов пробельных последовательностей. Доказанные результаты показаны в таблице выше.

Марк Аллен Вайс доказал, что сортировка Шелл выполняется за время O ( N log N ), когда входной массив находится в обратном порядке.

Что касается среднего количества операций, ни один из доказанных результатов не касается практической последовательности разрывов. Для разрывов, которые являются степенями двойки, Эспелид вычислил это среднее значение как $0.5349N{\sqrt {N}}-0.4387N-0.097{\sqrt {N}}+O(1)$. Кнут определил среднюю сложность сортировки массива из N элементов с двумя пробелами ( h , 1) как ${\frac {2N^{2}}{h}}+{\sqrt {\pi N^{3}h}}$. Отсюда следует, что двухпроходная сортировка Шелла с h = Θ( N ^1/3 ) составляет в среднем O ( N ^5/3 ) сравнения/инверсии/время выполнения. Яо нашел среднюю сложность трехпроходной сортировки Шелла. Его результат был уточнен Янсоном и Кнутом: среднее количество сравнений/инверсий/времени выполнения, выполненных во время сортировки Шелла с тремя пробелами ( ch , cg , 1), где h и g взаимно простые, равно ${\frac {N^{2}}{4ch}}+O(N)$ в первом проходе, ${\frac {1}{8g}}{\sqrt {\frac {\pi }{ch}}}(h-1)N^{3/2}+O(hN)$ во втором проходе и $\psi (h,g)N+{\frac {1}{8}}{\sqrt {\frac {\pi }{c}}}(c-1)N^{3/2}+O\left((c-1)gh^{1/2}N\right)+O\left(c^{2}g^{3}h^{2}\right)$ в третьем проходе. ψ ( h , g ) в последней формуле — сложная функция, асимптотически равная ${\sqrt {\frac {\pi h}{128}}}g+O\left(g^{-1/2}h^{1/2}\right)+O\left(gh^{-1/2}\right)$. В частности, когда h = Θ( N ^7/15 ) и g = Θ( N ^1/5 ), среднее время сортировки O ( N ^23/15 ).

На основании экспериментов предполагается, что сортировка Шелла с Хиббарда последовательностью пробелов выполняется за O ( N ^5/4 ) среднее время, и что последовательность Гонне и Баеза-Йейтса требует в среднем 0,41 N ln N (ln ln N + 1/6) перемещений элементов. Приближения среднего числа операций, ранее предложенные для других последовательностей, терпят неудачу, когда отсортированные массивы содержат миллионы элементов.

На графике ниже показано среднее количество сравнений элементов, используемых различными последовательностями пробелов, разделенное на теоретическую нижнюю границу , т. е. log ₂ N !. Последовательность Чуриа 1, 4, 10, 23, 57, 132, 301, 701 (обозначенная Ci01) была расширена в соответствии с формулой $h_{k}=\lfloor 2.25h_{k-1}\rfloor$.

Применяя теорию колмогоровской сложности , Цзян, Ли и Витаньи доказал следующую нижнюю оценку порядка среднего числа операций/времени выполнения в p- проходной сортировке Шелла: Ω( pN ^{1+1/ п} ), когда p ≤ log ₂ N , и Ω( pN ), когда > log ₂ N. p Таким образом, сортировка Шелл имеет перспективы работать за среднее время, которое асимптотически растет как N log N, только при использовании последовательностей с пробелами, количество пробелов в которых растет пропорционально логарифму размера массива. Однако неизвестно, сможет ли сортировка Шелла достичь этого асимптотического порядка сложности в среднем, который является оптимальным для сортировок сравнением. Нижняя граница была улучшена Витаньи. за каждое количество проходов $p$ к $\Omega (N\sum _{k=1}^{p}h_{k-1}/h_{k})$ где $h_{0}=N$. Из этого результата следует, например, нижняя граница Цзяна-Ли-Витаньи для всех $p$-пропустить последовательности приращений и улучшить нижнюю границу для конкретных последовательностей приращений. Фактически все границы (нижние и верхние), известные в настоящее время для среднего случая, точно совпадают с этой нижней границей. Например, это дает новый результат: верхняя граница Янсона-Кнута совпадает с результирующей нижней границей для используемой последовательности приращений, показывая, что трехпроходная сортировка Шелла для этой последовательности приращений использует $\Theta (N^{23/15})$ сравнения/инверсии/время выполнения. Формула позволяет нам искать последовательности приращений, которые дают неизвестные нижние границы; например, последовательность приращений для четырех проходов, нижняя граница которой превышает $\Omega (pn^{1+1/p})=\Omega (n^{5/4})$ для последовательности приращений $h_{1}=n^{11/16},$ $h_{2}=n^{7/16},$ $h_{3}=n^{3/16},$ $h_{4}=1$. Нижняя граница становится $T=\Omega (n\cdot (n^{1-11/16}+n^{11/16-7/16}+n^{7/16-3/16}+n^{3/16})=\Omega (n^{1+5/16})=\Omega (n^{21/16}).$

Наихудшая сложность любой версии сортировки Шелл имеет более высокий порядок: Плакстон, Пунен и Суэл показали, что она растет по крайней мере так же быстро, как $\Omega \left(N\left({\log N \over \log \log N}\right)^{2}\right)$. Роберт Сайфер доказал более сильную нижнюю оценку: $\Omega \left(N{{(\log N)^{2}} \over {\log \log N}}\right)$ когда $h_{s+1}>h_{s}$ для всех $s$.

Приложения

Shellsort выполняет больше операций и имеет более высокий коэффициент промахов в кэше, чем быстрая сортировка . Однако, поскольку она может быть реализована с использованием небольшого количества кода и не использует стек вызовов , некоторые реализации функции qsort в стандартной библиотеке C, предназначенные для встраиваемых систем, используют ее вместо быстрой сортировки. Например, сортировка Шелл используется в библиотеке uClibc . По тем же причинам в прошлом в ядре Linux использовалась Shellsort .

Сортировка Шелл также может служить подалгоритмом интроспективной сортировки для сортировки коротких подмассивов и предотвращения замедления работы, когда глубина рекурсии превышает заданный предел. Этот принцип используется, например, в компрессоре bzip2 .

См. также

• Гребенчатая сортировка

Библиография

• Кнут, Дональд Э. (1997). «Метод Шелла». Искусство компьютерного программирования. Том 3: Сортировка и поиск (2-е изд.). Ридинг, Массачусетс: Аддисон-Уэсли. стр. 83–95. ISBN  978-0-201-89685-5 .
• Анализ сортировки Шелла и связанных с ней алгоритмов , Роберт Седжвик, Четвертый европейский симпозиум по алгоритмам, Барселона, сентябрь 1996 г.

Внешние ссылки

• Анимированные алгоритмы сортировки: сортировка Шелла в Wayback Machine (архивировано 10 марта 2015 г.) - графическая демонстрация
• Шеллсорт с пробелами 5, 3, 1 как венгерский народный танец