Shellsort

Shellsort

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

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

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

Описание [ править ]

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

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

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

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

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

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

Псевдокод [ править ]

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

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

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

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

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

OEIS	Общий термин ( k ≥ 1)	Бетонные зазоры	Временная сложность наихудшего случая	Автор и год публикации
	${\displaystyle \left\lfloor {\frac {N}{2^{k}}}\right\rfloor }$	${\displaystyle \left\lfloor {\frac {N}{2}}\right\rfloor ,\left\lfloor {\frac {N}{4}}\right\rfloor ,\ldots ,1}$	${\displaystyle \Theta \left(N^{2}\right)}$[например, когда N = 2 p ]	Шелл , 1959 [4]
	${\displaystyle 2\left\lfloor {\frac {N}{2^{k+1}}}\right\rfloor +1}$	${\displaystyle 2\left\lfloor {\frac {N}{4}}\right\rfloor +1,\ldots ,3,1}$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Франк и Лазарь, 1960 [8]
A000225	${\displaystyle 2^{k}-1}$	${\displaystyle 1,3,7,15,31,63,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Хиббард , 1963 [9]
A083318	${\displaystyle 2^{k}+1}$, с префиксом 1	${\displaystyle 1,3,5,9,17,33,65,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Папернов и Стасевич, 1965 [10]
A003586	Последовательные числа формы ( 3-гладкие числа)${\displaystyle 2^{p}3^{q}}$	${\displaystyle 1,2,3,4,6,8,9,12,\ldots }$	${\displaystyle \Theta \left(N\log ^{2}N\right)}$	Пратт , 1971 год [1]
A003462	${\displaystyle {\frac {3^{k}-1}{2}}}$, не более ${\displaystyle \left\lceil {\frac {N}{3}}\right\rceil }$	${\displaystyle 1,4,13,40,121,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Knuth , 1973, [3] на основе Pratt , 1971 [1]
A036569	${\displaystyle {\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}}}$	${\displaystyle 1,3,7,21,48,112,\ldots }$	${\displaystyle O\left(N^{1+{\sqrt {\frac {8\ln \left(5/2\right)}{\ln(N)}}}}\right)}$	Incerpi & Sedgewick , 1985, [11] Knuth [3]
A036562	${\displaystyle 4^{k}+3\cdot 2^{k-1}+1}$, с префиксом 1	${\displaystyle 1,8,23,77,281,\ldots }$	${\displaystyle O\left(N^{\frac {4}{3}}\right)}$	Седжвик, 1982 [6]
A033622	${\displaystyle {\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}}}$	${\displaystyle 1,5,19,41,109,\ldots }$	${\displaystyle O\left(N^{\frac {4}{3}}\right)}$	Седжвик, 1986 [12]
	${\displaystyle h_{k}=\max \left\{\left\lfloor {\frac {5h_{k-1}-1}{11}}\right\rfloor ,1\right\},h_{0}=N}$	${\displaystyle \left\lfloor {\frac {5N-1}{11}}\right\rfloor ,\left\lfloor {\frac {5}{11}}\left\lfloor {\frac {5N-1}{11}}\right\rfloor -1\right\rfloor ,\ldots ,1}$	Неизвестный	Гоннет и Баеза-Йейтс , 1991 [13]
A108870	${\displaystyle \left\lceil {\frac {1}{5}}\left(9\cdot \left({\frac {9}{4}}\right)^{k-1}-4\right)\right\rceil }$	${\displaystyle 1,4,9,20,46,103,\ldots }$	Неизвестный	Токуда, 1992 [14]
A102549	Неизвестно (получено экспериментально)	${\displaystyle 1,4,10,23,57,132,301,701}$	Неизвестный	Чиура, 2001 [15]

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

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

Гоннет и Баеза-Йейтс заметили, что Shellsort в среднем делает наименьшее количество сравнений, когда отношение последовательных пропусков примерно равно 2,2. ^[13] Вот почему их последовательность с коэффициентом 2.2 и последовательность Токуды с коэффициентом 2.25 оказываются эффективными. Однако неизвестно, почему это так. Седжвик рекомендует использовать гэпы, которые имеют низкие наибольшие общие делители или попарно взаимно просты . ^{[16] [ неудачная проверка ]}

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

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

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

Вычислительная сложность [ править ]

Имеет место следующее свойство: после h ₂ -сортировки любого h ₁ -сортированного массива массив остается h ₁ -сортированным. ^[18] Каждый h ₁ -сортированный и h ₂ -сортированный массив также ( a ₁ h ₁ + a ₂ h ₂ ) -сортированный для любых неотрицательных целых чисел a ₁ и a ₂ . Таким образом, наихудшая сложность Shellsort связана с проблемой Фробениуса : для заданных целых чисел h ₁ , ..., h _nс НОД = 1, число Фробениуса г ( ч ₁ , ..., ч _п ) наибольшее целое число , которое не может быть представлено как в ₁ ч ₁ + ... + _п ч _п с целыми неотрицательными ₁ , .. ., а _н . Используя известные формулы для чисел Фробениуса, мы можем определить наихудшую сложность Shellsort для нескольких классов разрывных последовательностей. ^[19] Подтвержденные результаты показаны в таблице выше.

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

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

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

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

Наихудшая сложность любой версии Shellsort - более высокого порядка: Plaxton, Poonen и Suel показали, что она растет по крайней мере так же быстро, как . ^{[25] [26]}${\displaystyle \Omega \left(N\left({\log N \over \log \log N}\right)^{2}\right)}$

Приложения [ править ]

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

Shellsort также может служить под-алгоритмом интроспективной сортировки для сортировки коротких подмассивов и предотвращения замедления, когда глубина рекурсии превышает заданный предел. Этот принцип используется, например, в компрессоре bzip2 . ^[29]

См. Также [ править ]

• Расческа сортировка

Ссылки [ править ]

Библиография [ править ]

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

Внешние ссылки [ править ]

В реализации алгоритма Викибука есть страница по теме: Сортировка по оболочке

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