WikiDer > Shellsort - Википедия

Shellsort

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

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

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

Описание

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

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

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

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

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

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

Псевдокод

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

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

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

Вопрос о том, какую последовательность пробелов использовать, является трудным. Каждая последовательность пробелов, содержащая 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п]	Ракушка, 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	Последовательные числа формы ${ displaystyle 2 ^ {p} 3 ^ {q}}$ (3-гладкий числа)	${ 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] на основе Пратт, 1971[1]
A036569	${ displaystyle { begin {align} & prod limits _ {I} a_ {q}, { hbox {where}} a_ {0} = {} & 3 a_ {q} = {} & min left {n in mathbb {N} двоеточие n geq left ({ frac {5} {2}} right) ^ {q + 1}, forall p двоеточие 0 leq p$	${ 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 {case}}}$	${ 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}} {11}} right rfloor, 1 right }, h_ {0} = N }$	${ displaystyle left lfloor { frac {5N} {11}} right rfloor, left lfloor { frac {5} {11}} left lfloor { frac {5N} {11}} right rfloor 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 равняется степени двойки, когда элементы больше и меньше медианы занимают нечетные и четные позиции соответственно, поскольку они сравниваются только на последнем проходе.

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

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

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

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

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

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

Что касается среднего количества операций, ни один из доказанных результатов не касается практической последовательности пропусков. Для пробелов, равных степени двойки, Эспелид вычислил это среднее как ${ displaystyle 0,5349N { sqrt {N}} - 0,4387N-0,097 { sqrt {N}} + O (1)}$.^[19] Knuth определила среднюю сложность сортировки N-элементный массив с двумя пробелами (час, 1) быть ${ displaystyle { frac {2N ^ {2}} {h}} + { sqrt { pi N ^ {3} h}}}$.^[3] Отсюда следует, что двухпроходная сортировка Shellsort с час = Θ (N^1/3) составляет в среднем О(N^5/3) сравнения / инверсии / время работы. Яо нашли среднюю сложность трехпроходной сортировки Shellsort.^[20] Его результат был уточнен Янсоном и Кнутом:^[21] среднее количество сравнений / инверсий / время выполнения, сделанных во время Shellsort с тремя пробелами (ch, cg, 1), где час и грамм взаимно просты, является ${ 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)}$. В частности, когда час = Θ (N^7/15) и грамм = Θ (N^1/5) среднее время сортировки О(N^23/15).

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

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

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

Приложения

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

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

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

• Сортировка гребней

Рекомендации

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

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

внешняя ссылка

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

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