Сортировка по методу Шелла
Алгоритм сортировки, использующий несколько интервалов сравнения
Сортировка по методу Шелла
Пошаговая визуализация сортировки Шелла
Сортировка Шелла с пропусками 23, 10, 4, 1 в действии
СортАлгоритм сортировки
Структура данныхМножество
Худший вариант производительностиO( n 2 ) (наихудшая известная последовательность зазоров в худшем случае)
O( n log 2 n ) (наиболее известная последовательность зазоров в худшем случае) [1]
Лучшая производительностьO( n log n ) (большинство последовательностей зазоров)
O( n log 2 n ) (самая известная наихудшая последовательность зазоров) [2]
Средняя производительностьзависит от последовательности пробелов
Наихудшая сложность пространстваО( n ) всего, О(1) вспомогательных
ОптимальныйНет
Этапы сортировки по методу Шелла.
Перестановка пар элементов в последовательных шагах сортировки Шелла с промежутками 5, 3, 1

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

Описание

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

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

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

а 1а 2а 3а 4а 5а 6а 7а 8а 9а 10а 11а 12
Входные данные628318530717958647692528
После 5-сортировки172818470725838653696295
После 3-й сортировки170718472825696253838695
После 1-сортировки071718252847536269838695

Первый проход, 5-сортировка, выполняет сортировку вставкой для пяти отдельных подмассивов ( a 1 , a 6 , a 11 ), ( a 2 , a 7 , a 12 ), ( a 3 , a 8 ), ( a 4 , a 9 ), ( a 5 , a 10 ). Например, он изменяет подмассив ( a 1 , a 6 , a 11 ) с (62, 17, 25) на (17, 25, 62). Следующий проход, 3-сортировка, выполняет сортировку вставкой для трех подмассивов ( a 1 , a 4 , a 7 , a 10 ), ( a 2 , a 5 , a 8 , a 11 ), ( a 3 , a 6 , a 9 , a 12 ). Последний проход, 1-сортировка, представляет собой обычную сортировку вставкой всего массива ( a 1 ,..., a 12 ).

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

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

Псевдокод

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

# Сортировка массива a[0...n-1]. gaps = [ 701 , 301 , 132 , 57 , 23 , 10 , 4 , 1 ] # Последовательность пробелов Сиуры             # Начинаем с самого большого пробела и уменьшаем до пробела 1 # аналогично сортировке вставкой, но вместо 1 на каждом шаге используется пробел foreach ( gap in gaps ) { # Выполняем сортировку вставкой с пробелами для каждого элемента в gaps # Каждый цикл оставляет a[0..gap-1] в порядке с пробелами for ( i = gap ; i < n ; i += 1 ) { # сохраняем a[i] в ​​temp и создаем пробел в позиции i temp = a [ i ] # сдвигаем ранее отсортированные по пробелам элементы вверх, пока не будет найдено правильное местоположение для a[i] for ( j = i ; ( j >= gap ) && ( a [ j - gap ] > temp ); j ​​-= gap ) { a [ j ] = a [ j - gap ] } # помещаем temp (исходный a[i]) в правильное местоположение a [ j ] = temp } }

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

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

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

ОЭИСОбщий термин ( k ≥ 1)Бетонные щелиНаихудшая
временная сложность		Автор и год публикации
⌊ Н 2 к ⌋ {\displaystyle \left\lfloor {\frac {N}{2^{k}}}\right\rfloor } 1 , 2 , … , ⌊ Н 4 ⌋ , ⌊ Н 2 ⌋ {\displaystyle 1,2,\ldots ,\left\lfloor {\frac {N}{4}}\right\rfloor ,\left\lfloor {\frac {N}{2}}\right\rfloor } Θ ( Н 2 ) {\displaystyle \Тета \left(N^{2}\right)} [например, когда N = 2 p ]Шелл , 1959 [4]
2 ⌊ Н 2 к + 1 ⌋ + 1 {\displaystyle 2\left\lfloor {\frac {N}{2^{k+1}}}\right\rfloor +1} 1 , 3 , … , 2 ⌊ Н 8 ⌋ + 1 , 2 ⌊ Н 4 ⌋ + 1 {\displaystyle 1,3,\ldots ,\;2\left\lfloor {\frac {N}{8}}\right\rfloor +1,\;\;2\left\lfloor {\frac {N}{4}}\right\rfloor +1} Θ ( Н 3 2 ) {\displaystyle \Theta \left(N^{\frac {3}{2}}\right)} Фрэнк и Лазарус, 1960 [8]
А000225 2 к − 1 {\displaystyle 2^{k}-1} 1 , 3 , 7 , 15 , 31 , 63 , … {\displaystyle 1,3,7,15,31,63,\ldots } Θ ( Н 3 2 ) {\displaystyle \Theta \left(N^{\frac {3}{2}}\right)} Хиббард , 1963 [9]
А083318 2 к + 1 {\displaystyle 2^{k}+1} , с префиксом 1 1 , 3 , 5 , 9 , 17 , 33 , 65 , … {\displaystyle 1,3,5,9,17,33,65,\ldots} Θ ( Н 3 2 ) {\displaystyle \Theta \left(N^{\frac {3}{2}}\right)} Папернов и Стасевич, 1965 [10]
А003586Последовательные числа вида ( 3-гладкие числа) 2 п 3 д {\displaystyle 2^{p}3^{q}} 1 , 2 , 3 , 4 , 6 , 8 , 9 , 12 , … {\displaystyle 1,2,3,4,6,8,9,12,\ldots} Θ ( Н бревно 2 ⁡ Н ) {\displaystyle \Theta \left(N\log ^{2}N\right)} Пратт , 1971 [1]
А003462 3 к − 1 2 {\displaystyle {\frac {3^{k}-1}{2}}} , не более ⌈ Н 3 ⌉ {\displaystyle \left\lceil {\frac {N}{3}}\right\rceil } 1 , 4 , 13 , 40 , 121 , … {\displaystyle 1,4,13,40,121,\ldots} Θ ( Н 3 2 ) {\displaystyle \Theta \left(N^{\frac {3}{2}}\right)} Кнут , 1973, [3] на основе Пратта , 1971 [1]
А036569 ∏ я а д , где а 0 = 3 а д = мин { н ∈ Н : н ≥ ( 5 2 ) д + 1 , ∀ п : 0 ≤ п < д ⇒ gcd ( а п , н ) = 1 } я = { 0 ≤ д < г ∣ д ≠ 1 2 ( г 2 + г ) − к } г = ⌊ 2 к + 2 к ⌋ {\displaystyle {\begin{aligned}&\prod \limits _{I}a_{q},{\hbox{где}}\\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{выровнено}}} 1 , 3 , 7 , 21 , 48 , 112 , … {\displaystyle 1,3,7,21,48,112,\ldots} О ( Н 1 + 8 вн ⁡ ( 5 / 2 ) вн ⁡ ( Н ) ) {\displaystyle O\left(N^{1+{\sqrt {\frac {8\ln \left(5/2\right)}{\ln(N)}}}}\right)} Инсерпи и Седжвик , 1985, [11] Кнут [3]
А036562 4 к + 3 ⋅ 2 к − 1 + 1 {\displaystyle 4^{k}+3\cdot 2^{k-1}+1} , с префиксом 1 1 , 8 , 23 , 77 , 281 , … {\displaystyle 1,8,23,77,281,\ldots} О ( Н 4 3 ) {\displaystyle O\left(N^{\frac {4}{3}}\right)} Седжвик, 1982 [6]
А033622 { 9 ( 2 к − 2 к 2 ) + 1 к  даже , 8 ⋅ 2 к − 6 ⋅ 2 ( к + 1 ) / 2 + 1 к  странный {\displaystyle {\begin{cases}9\left(2^{k}-2^{\frac {k}{2}}\right)+1&k{\text{ четный}},\\8\cdot 2^{k}-6\cdot 2^{(k+1)/2}+1&k{\text{ нечетный}}\end{cases}}} 1 , 5 , 19 , 41 , 109 , … {\displaystyle 1,5,19,41,109,\ldots} О ( Н 4 3 ) {\displaystyle O\left(N^{\frac {4}{3}}\right)} Седжвик, 1986 [12]
час к = макс { ⌊ 5 час к − 1 − 1 11 ⌋ , 1 } , час 0 = Н {\displaystyle h_{k}=\max \left\{\left\lfloor {\frac {5h_{k-1}-1}{11}}\right\rfloor ,1\right\},h_{0}=N} 1 , … , ⌊ 5 11 ⌊ 5 Н − 1 11 ⌋ − 1 11 ⌋ , ⌊ 5 Н − 1 11 ⌋ {\displaystyle 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 } НеизвестныйГоннет и Баеза-Йейтс , 1991 [13]
А108870 ⌈ 1 5 ( 9 ⋅ ( 9 4 ) к − 1 − 4 ) ⌉ {\displaystyle \left\lceil {\frac {1}{5}}\left(9\cdot \left({\frac {9}{4}}\right)^{k-1}-4\right)\right\rceil } (или эквивалентно, ) ⌈ ( 9 / 4 ) к − 1 ( 9 / 4 ) − 1 ⌉ {\displaystyle \left\lceil {\frac {\left(9/4\right)^{k}-1}{\left(9/4\right)-1}}\right\rceil } 1 , 4 , 9 , 20 , 46 , 103 , … {\displaystyle 1,4,9,20,46,103,\ldots } НеизвестныйТокуда, 1992 г. [14] (неправильная цитата согласно OEIS)
А102549Неизвестно (получено экспериментально) 1 , 4 , 10 , 23 , 57 , 132 , 301 , 701 {\displaystyle 1,4,10,23,57,132,301,701} НеизвестныйСиура, 2001 [15]
А366726 ⌈ γ k − 1 γ − 1 ⌉ , γ = 2.243609061420001 … {\displaystyle \left\lceil {\frac {\gamma ^{k}-1}{\gamma -1}}\right\rceil ,\gamma =2.243609061420001\ldots } 1 , 4 , 9 , 20 , 45 , 102 , 230 , 516 , … {\displaystyle 1,4,9,20,45,102,230,516,\ldots } НеизвестныйЛи, 2021 [16]
⌊ 4.0816 ⋅ 8.5714 k 2.2449 ⌋ {\displaystyle \left\lfloor 4.0816\cdot 8.5714^{\frac {k}{2.2449}}\right\rfloor } 1 , 4 , 10 , 27 , 72 , 187 , 488 , … {\displaystyle 1,4,10,27,72,187,488,\ldots } НеизвестныйСкин, Эренборг, Яромчик, 2023 г. [17]

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

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

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

Что касается среднего числа сравнений, то последовательность Сиуры [15] имеет наилучшую известную производительность; пробелы больше 701 не были определены, но последовательность может быть дополнительно расширена в соответствии с рекурсивной формулой . h k = ⌊ 2.25 h k − 1 ⌋ {\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }

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

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

Сложность вычислений

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

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

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

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

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

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

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

Приложения

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

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

Смотрите также

Ссылки

  1. ^ abc Pratt, Vaughan Ronald (1979). Сортировка Шелла и сортировочные сети (Выдающиеся диссертации по компьютерным наукам) (PDF) . Garland. ISBN 978-0-8240-4406-0. Архивировано (PDF) из оригинала 7 сентября 2021 г.
  2. ^ "Сортировка Шелла и сравнения". Архивировано из оригинала 20 декабря 2019 года . Получено 14 ноября 2015 года .
  3. ^ abcde Кнут, Дональд Э. (1997). «Метод Шелла». Искусство программирования. Том 3: Сортировка и поиск (2-е изд.). Reading, Массачусетс: Addison-Wesley. С. 83–95. ISBN 978-0-201-89685-5.
  4. ^ ab Shell, DL (1959). "A High-Speed ​​Sorting Procedure" (PDF) . Communications of the ACM . 2 (7): 30–32. doi :10.1145/368370.368387. S2CID  28572656. Архивировано из оригинала (PDF) 30 августа 2017 г. . Получено 18 октября 2011 г. .
  5. ^ Некоторые старые учебники и справочники называют это сортировкой «Шелл–Мецнер» в честь Марлен Мецнер Нортон, но, по словам Мецнер, «я не имела никакого отношения к этой сортировке, и мое имя никогда не должно было быть связано с ней». См. «Сортировка Шелла». Национальный институт стандартов и технологий . Получено 17 июля 2007 г.
  6. ^ abc Седжвик, Роберт (1998). Алгоритмы в C. Т. 1 (3-е изд.). Эддисон-Уэсли. С. 273–281. ISBN  978-0-201-31452-6.
  7. ^ Керниган, Брайан В .; Ритчи, Деннис М. (1996). Язык программирования C (2-е изд.). Prentice Hall. стр. 62. ISBN  978-7-302-02412-5.
  8. ^ Фрэнк, Р. М.; Лазарус, Р. Б. (1960). «Процедура высокоскоростной сортировки». Сообщения ACM . 3 (1): 20–22. doi : 10.1145/366947.366957 . S2CID  34066017.
  9. ^ Хиббард, Томас Н. (1963). «Эмпирическое исследование сортировки с минимальным хранением». Сообщения ACM . 6 (5): 206–213. doi : 10.1145/366552.366557 . S2CID  12146844.
  10. ^ Папернов, А.А.; Стасевич, Г.В. (1965). «Метод сортировки информации в запоминающих устройствах ЭВМ» (PDF) . Проблемы передачи информации . 1 (3): 63–75.
  11. ^ Инсерпи, Джанет; Седжвик, Роберт (1985). «Улучшенные верхние границы сортировки Шелла» (PDF) . Журнал компьютерных и системных наук . 31 (2): 210–224. doi :10.1016/0022-0000(85)90042-x.
  12. ^ Седжвик, Роберт (1986). «Новая верхняя граница для сортировки Шелла». Журнал алгоритмов . 7 (2): 159–173. doi :10.1016/0196-6774(86)90001-5.
  13. ^ abc Gonnet, Gaston H.; Baeza-Yates, Ricardo (1991). «Сортировка Шелла». Справочник по алгоритмам и структурам данных: на Паскале и C (2-е изд.). Reading, Massachusetts: Addison-Wesley. стр. 161–163. ISBN 978-0-201-41607-7. Обширные эксперименты показывают, что последовательность, определяемая как α = 0,45454 < 5/11, работает значительно лучше, чем другие последовательности. Самый простой способ вычислить ⌊ 0,45454 n ⌋ — использовать целочисленную арифметику.(5 * n — 1)/11
  14. ^ Токуда, Наоюки (1992). «Улучшенная сортировка Шелла». В ван Леувене, Ян (ред.). Труды IFIP 12-го Всемирного компьютерного конгресса по алгоритмам, программному обеспечению, архитектуре . Амстердам: North-Holland Publishing Co. стр. 449–457. ISBN 978-0-444-89747-3.
  15. ^ ab Ciura, Marcin (2001). "Лучшие приращения для среднего случая сортировки Шелла" (PDF) . В Freiwalds, Rusins ​​(ред.). Труды 13-го Международного симпозиума по основам теории вычислений . Лондон: Springer-Verlag. С. 106–117. ISBN 978-3-540-42487-1. Архивировано из оригинала (PDF) 23 сентября 2018 года.
  16. ^ Ли, Ин Вай (21 декабря 2021 г.). «Эмпирически улучшенная последовательность разрывов Токуды в сортировке Шелла». arXiv : 2112.11112 [cs.DS].
  17. ^ Скин, Оскар; Эренборг, Ричард; Яромчик, Ежи В. (1 января 2023 г.). «Перспективы оптимизации сортировки Шелла». arXiv : 2301.00316 [cs.DS].
  18. ^ Седжвик, Роберт (1998). «Сортировка Шелла». Алгоритмы в C++, части 1–4: Основы, Структура данных, Сортировка, Поиск . Reading, Массачусетс: Addison-Wesley. стр. 285–292. ISBN 978-0-201-35088-3.
  19. ^ Форшелл, Олоф (22 мая 2018 г.). «Как выбрать длину моих подпоследовательностей для сортировки Шелла?». Stack Overflow . Дополнительный комментарий в разделе Самая быстрая последовательность пробелов для сортировки Шелла? (23 мая 2018 г.).
  20. ^ Ли, Ин Вай (21 декабря 2021 г.). «Оптимальные последовательности зазоров в сортировке Шелла для n ≤ 16 элементов». arXiv : 2112.11127 [math.CO].
  21. ^ Гейл, Дэвид ; Карп, Ричард М. (апрель 1972 г.). "Явление в теории сортировки" (PDF) . Журнал компьютерных и системных наук . 6 (2): 103–115. doi : 10.1016/S0022-0000(72)80016-3 .
  22. ^ Selmer, Ernst S. (март 1989). «О сортировке Шелла и проблеме Фробениуса» (PDF) . BIT Numerical Mathematics . 29 (1): 37–40. doi :10.1007/BF01932703. hdl : 1956/19572 . S2CID  32467267.
  23. ^ Вайс, Марк Аллен (1989). «Хороший случай для Shellsort». Конгресс Нумерантиум . 73 : 59–62.
  24. ^ Эспелид, Терье О. (декабрь 1973 г.). «Анализ алгоритма сортировки Шелла». BIT Numerical Mathematics . 13 (4): 394–400. doi :10.1007/BF01933401. S2CID  119443598. Приведенный результат — уравнение (8) на стр. 399.
  25. ^ Яо, Эндрю Чи-Чи (1980). "Анализ (h, k, 1)-сортировки Шелла" (PDF) . Журнал алгоритмов . 1 (1): 14–50. doi :10.1016/0196-6774(80)90003-6. S2CID  3054966. STAN-CS-79-726. Архивировано из оригинала (PDF) 4 марта 2019 г.
  26. ^ Янсон, Сванте ; Кнут, Дональд Э. (1997). «Сортировка Шелла с тремя приращениями» (PDF) . Случайные структуры и алгоритмы . 10 (1–2): 125–142. arXiv : cs/9608105 . CiteSeerX 10.1.1.54.9911 . doi :10.1002/(SICI)1098-2418(199701/03)10:1/2<125::AID-RSA6>3.0.CO;2-X. 
  27. ^ Цзян, Тао; Ли, Мин ; Витаньи, Пол (сентябрь 2000 г.). «Нижняя граница средней сложности сортировки Шелла» (PDF) . Журнал АКМ . 47 (5): 905–911. arXiv : cs/9906008 . CiteSeerX 10.1.1.6.6508 . дои : 10.1145/355483.355488. S2CID  3265123. 
  28. ^ Витаний, Пол (март 2018 г.). «О средней сложности сортировки Шелла» (PDF) . Случайные структуры и алгоритмы . 52 (2): 354–363. arXiv : 1501.06461 . doi : 10.1002/rsa.20737. S2CID  6833808.
  29. ^ Plaxton, C. Greg; Poonen, Bjorn ; Suel, Torsten (24–27 октября 1992 г.). «Улучшенные нижние границы для сортировки Шелла» (PDF) . Труды., 33-й ежегодный симпозиум по основам компьютерной науки . Том 33. Питтсбург, США. стр. 226–235. CiteSeerX 10.1.1.43.1393 . doi :10.1109/SFCS.1992.267769. ISBN  978-0-8186-2900-6. S2CID  15095863.{{cite book}}: CS1 maint: location missing publisher (link)
  30. ^ Plaxton, C. Greg; Suel, Torsten (май 1997 г.). "Нижние границы для сортировки Шелла" (PDF) . Журнал алгоритмов . 23 (2): 221–240. CiteSeerX 10.1.1.460.2429 . doi :10.1006/jagm.1996.0825. 
  31. ^ Cypher, Robert (1993). «Нижняя граница размера сетей сортировки Шелла». SIAM Journal on Computing . 22 : 62–71. doi :10.1137/0222006.
  32. ^ Новоа, Мануэль III. "libc/stdlib/stdlib.c" . Проверено 29 октября 2014 г.
  33. ^ "kernel/groups.c". GitHub . Получено 5 мая 2012 .
  34. ^ Джулиан Сьюард. "bzip2/blocksort.c" . Получено 30 марта 2011 г.

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

Реализация алгоритма Wikibook имеет страницу по теме: Сортировка Шелла
  • Анимированные алгоритмы сортировки: сортировка Шелла на машине Wayback (архив 10 марта 2015 г.) – графическая демонстрация
  • Сортировка Шелла с пропусками 5, 3, 1 как венгерский народный танец

Retrieved from "https://en.wikipedia.org/w/index.php?title=Shellsort&oldid=1224257594"