Сортировка Шелла
TL;DR
Сортировка Шелла (Shellsort) — обобщение сортировки вставками: массив сортируется вставками не по одному, а по подпоследовательностям с убывающим шагом (gap) [math]\displaystyle{ h, \dots, 1 }[/math]. Большие шаги переносят элементы на далёкие расстояния и устраняют «дальние» инверсии; когда доходит до [math]\displaystyle{ h = 1 }[/math], массив уже почти упорядочен, и финальный проход вставок дёшев. Алгоритм работает на месте ([math]\displaystyle{ O(1) }[/math] памяти), без рекурсии, прост в реализации и адаптивен; его скорость определяется последовательностью шагов. Худший случай — от [math]\displaystyle{ \Theta(n^2) }[/math] (плохие шаги, например степени двойки) до [math]\displaystyle{ \Theta(n^{4/3}) }[/math] и [math]\displaystyle{ \Theta(n\log^2 n) }[/math] (хорошие шаги), на практике — около [math]\displaystyle{ O(n^{1.3}) }[/math] при последовательности Ciura. Сортировка Шелла неустойчива и уступает [math]\displaystyle{ O(n\log n) }[/math]-сортировкам на больших массивах, но выигрывает там, где важны простота и [math]\displaystyle{ O(1) }[/math] памяти.
| Свойство | Значение |
|---|---|
| Класс | Сортировка сравнением; на месте; без рекурсии |
| Обобщает | сортировку вставками (случай одного шага [math]\displaystyle{ h=1 }[/math]) |
| Автор | Дональд Шелл (Donald L. Shell), 1959 |
| Лучший случай | [math]\displaystyle{ \Theta(n \cdot k) }[/math] для [math]\displaystyle{ k }[/math] проходов; на почти отсортированном массиве каждый проход линеен |
| Средний случай | зависит от шагов, часто [math]\displaystyle{ \approx n^{1.25} }[/math]–[math]\displaystyle{ n^{1.5} }[/math] |
| Худший случай | от [math]\displaystyle{ \Theta(n^2) }[/math] до [math]\displaystyle{ \Theta(n\log^2 n) }[/math] — зависит от последовательности шагов |
| Память | [math]\displaystyle{ O(1) }[/math] |
| Устойчивость | нет (элементы прыгают через соседей) |
| Ключ к скорости | выбор последовательности шагов |
| Лучшая практика | последовательность Ciura (1, 4, 10, 23, 57, 132, 301, 701, …) |
| Родственники | introsort/Timsort (используют вставки, не Шелл), Быстрая сортировка |
Определения
Сортировка Шелла (Shellsort) — алгоритм, который выполняет несколько проходов сортировки вставками по подпоследовательностям, выделяемым с убывающим шагом [math]\displaystyle{ h }[/math]; последний проход имеет шаг [math]\displaystyle{ h = 1 }[/math] и завершает сортировку.
Шаг (gap, increment) [math]\displaystyle{ h }[/math] — расстояние между соседними элементами подпоследовательности. При шаге [math]\displaystyle{ h }[/math] сравниваются и переставляются элементы [math]\displaystyle{ a[i] }[/math] и [math]\displaystyle{ a[i+h] }[/math].
[math]\displaystyle{ h }[/math]-упорядоченность ([math]\displaystyle{ h }[/math]-sorted). Массив [math]\displaystyle{ h }[/math]-упорядочен, если каждая из [math]\displaystyle{ h }[/math] подпоследовательностей [math]\displaystyle{ \{a[i], a[i+h], a[i+2h], \dots\} }[/math] отсортирована, то есть [math]\displaystyle{ a[i] \le a[i+h] }[/math] для всех допустимых [math]\displaystyle{ i }[/math].
Последовательность шагов (increment sequence) — убывающий список [math]\displaystyle{ h_1 \gt h_2 \gt \dots \gt h_k = 1 }[/math]; гарантией корректности служит [math]\displaystyle{ h_k = 1 }[/math].
Сортировка вставками с шагом [math]\displaystyle{ h }[/math] ([math]\displaystyle{ h }[/math]-sort). Один проход: для каждого [math]\displaystyle{ i }[/math] от [math]\displaystyle{ h }[/math] до [math]\displaystyle{ n-1 }[/math] вставляем [math]\displaystyle{ a[i] }[/math] в подпоследовательность с шагом [math]\displaystyle{ h }[/math] сдвигами на [math]\displaystyle{ h }[/math] позиций.
Устойчивость. Шелл неустойчив: при шаге [math]\displaystyle{ h \gt 1 }[/math] элементы перемещаются через соседей, и порядок равных может измениться (в отличие от обычных вставок).
Обозначения. [math]\displaystyle{ n }[/math] — длина массива; [math]\displaystyle{ h }[/math] — текущий шаг; [math]\displaystyle{ k }[/math] — число проходов; [math]\displaystyle{ \log }[/math] — двоичный.
Мотивация и интуиция
Обычная сортировка вставками смещает элемент на одну позицию за раз: если маленький элемент стоит в конце, ему нужно [math]\displaystyle{ n }[/math] сдвигов, что и даёт [math]\displaystyle{ \Theta(n^2) }[/math]. Идея Шелла: сначала переставлять элементы на большие расстояния, чтобы убрать крупные «дальние» инверсии малой ценой, а затем досортировать «ближние» дешёвыми проходами (см. рис. 1).
Ключевое наблюдение: сортировка вставками быстра на почти отсортированных данных. Значит, если после грубых проходов массив стал «почти отсортированным», финальный проход [math]\displaystyle{ h = 1 }[/math] будет дешёвым. Чем лучше выбраны шаги, тем более упорядоченным приходит массив к последнему проходу (см. рис. 2).
Идея в одном абзаце: несколько проходов вставок с убывающим шагом. Крупные шаги делают работу, пропорциональную числу дальних инверсий, мелкие — ближних; в сумме получается заметно быстрее [math]\displaystyle{ \Theta(n^2) }[/math], хотя точная сложность зависит от последовательности шагов.
Устройство
Шелл — это цикл по убывающим шагам, внутри которого делается стандартная сортировка вставками, но со сдвигом на [math]\displaystyle{ h }[/math] (см. рис. 1). Последний шаг всегда [math]\displaystyle{ h = 1 }[/math].
Почему важны именно шаги: при степенях двойки ([math]\displaystyle{ n/2, n/4, \dots }[/math]) массив долго остаётся «разложенным» так, что эффективность падает до [math]\displaystyle{ \Theta(n^2) }[/math]; шаги вида [math]\displaystyle{ 2^k-1 }[/math] (Hibbard) дают [math]\displaystyle{ \Theta(n^{3/2}) }[/math]; специальные формулы (Sedgewick) — [math]\displaystyle{ O(n^{4/3}) }[/math]; эмпирическая последовательность Ciura лучше всех на практике для средних [math]\displaystyle{ n }[/math] (см. рис. 3).
Вариант с двумя массивами: можно сортировать в отдельном буфере (для маленьких ключей это иногда быстрее), но классический Шелл обходится [math]\displaystyle{ O(1) }[/math] памяти.
Операции и алгоритмы
Операция: Shellsort (по последовательности шагов)
Идея. Для каждого шага [math]\displaystyle{ h }[/math] из последовательности выполнить [math]\displaystyle{ h }[/math]-sort (вставки со сдвигом [math]\displaystyle{ h }[/math]).
Пошаговое описание:
- Получить последовательность шагов [math]\displaystyle{ h_1 \gt h_2 \gt \dots \gt 1 }[/math].
- Для каждого шага [math]\displaystyle{ h }[/math]: для [math]\displaystyle{ i }[/math] от [math]\displaystyle{ h }[/math] до [math]\displaystyle{ n-1 }[/math] вставить [math]\displaystyle{ a[i] }[/math] в подпоследовательность с шагом [math]\displaystyle{ h }[/math], сдвигая большие элементы на [math]\displaystyle{ h }[/math] позиций вправо.
Инвариант. После прохода с шагом [math]\displaystyle{ h }[/math] массив [math]\displaystyle{ h }[/math]-упорядочен; предыдущие (более крупные) шаги сохраняются (лемма Кнута, см. «Корректность»).
Алгоритм Shellsort(a, gaps)
Вход: массив a[0..n−1]; последовательность шагов gaps, оканчивающаяся 1
Выход: a отсортирован
Инвариант: после шага h подпоследовательности с шагом h отсортированы
Сложность: зависит от gaps (см. таблицу)
1 for each h ∈ gaps # от больших к меньшим, последний = 1
2 for i ← h to n − 1
3 v ← a[i]
4 j ← i − h
5 while j ≥ 0 and a[j] > v # строгое > (устойчивость внутри прохода не гарантирует
6 a[j + h] ← a[j] # устойчивости всего алгоритма при h > 1)
7 j ← j − h
8 a[j + h] ← v
Разбор. На рис. 4: [35,33,42,10,14,19,27,44], шаги 4, 1. После h=4: [14,19,27,10,35,33,42,44]; после h=1 — [10,14,19,27,33,35,42,44].
Сложность. Один [math]\displaystyle{ h }[/math]-sort стоит [math]\displaystyle{ O(n) }[/math] на «хорошо упорядоченном» массиве; суммарно зависит от числа и величины шагов (см. таблицу).
Крайние случаи. [math]\displaystyle{ n \le 1 }[/math] — ничего. Пропущенный шаг [math]\displaystyle{ h=1 }[/math] оставляет массив несортированным.
Операция: генерация последовательности шагов
Идея. Построить убывающий список шагов, оканчивающийся единицей, по выбранному правилу роста.
Пошаговое описание:
- Положить [math]\displaystyle{ h = 1 }[/math].
- Пока [math]\displaystyle{ h \lt n }[/math]: добавить [math]\displaystyle{ h }[/math] в список и заменить [math]\displaystyle{ h \leftarrow 3h+1 }[/math].
- Развернуть список, чтобы шаги шли от больших к меньшим.
- Убедиться, что последний элемент списка равен 1.
Инвариант. Все шаги положительны и убывают после разворота; последний шаг равен 1.
Сложность. [math]\displaystyle{ O(\log n) }[/math] шагов и [math]\displaystyle{ O(\log n) }[/math] памяти под список: каждый следующий шаг не меньше утроенного предыдущего, поэтому длина списка логарифмическая.
Крайние случаи. [math]\displaystyle{ n \le 1 }[/math] — список шагов пуст, сортировать нечего.
Knuth (3h+1): 1, 4, 13, 40, 121, … — начиная с 1, пока [math]\displaystyle{ h \lt n }[/math], строим [math]\displaystyle{ h \leftarrow 3h+1 }[/math], затем разворачиваем. Худший случай [math]\displaystyle{ \Theta(n^{3/2}) }[/math], простая и надёжная.
Hibbard ([math]\displaystyle{ 2^k-1 }[/math]): 1, 3, 7, 15, 31, … — [math]\displaystyle{ \Theta(n^{3/2}) }[/math], но на практике чуть хуже Knuth.
Sedgewick (1986): последовательности вида [math]\displaystyle{ 4^k \pm O(2^k) }[/math]; дают [math]\displaystyle{ O(n^{4/3}) }[/math] в худшем случае.
Ciura (2001): 1, 4, 10, 23, 57, 132, 301, 701, … (эмпирически найденные); для больших [math]\displaystyle{ n }[/math] продолжают умножением на [math]\displaystyle{ \approx 2.25 }[/math]. Лучшая практическая последовательность.
Функция Knuth-Gaps(n)
Вход: n — длина массива, n ≥ 0
Выход: убывающий список шагов; при n ≥ 2 последний элемент равен 1
Инвариант: добавленные шаги положительны и возрастают
Сложность: O(log n) шагов, O(log n) памяти
1 gaps ← []
2 h ← 1
3 while h < n: gaps.append(h); h ← 3·h + 1
4 reverse(gaps) # от больших к 1
5 return gaps
Корректность: h монотонно растёт, цикл конечен; после разворота шаги убывают, а последним в списке оказывается 1 — первый добавленный шаг.
Разбор. Для [math]\displaystyle{ n = 8 }[/math]: [math]\displaystyle{ h = 1 \lt 8 }[/math] → [1], [math]\displaystyle{ h = 4 }[/math]; [math]\displaystyle{ 4 \lt 8 }[/math] → [1, 4], [math]\displaystyle{ h = 13 }[/math]; разворот даёт [4, 1].
Варианты и замечания
- Tokuda (1992):
1, 4, 9, 20, 46, 103, …— эмпирическое правило роста [math]\displaystyle{ \approx 2.25 }[/math]; даёт [math]\displaystyle{ O(n^{5/4}) }[/math] в худшем случае. - Двухмассивный Шелл: можно сортировать в отдельном буфере, перекладывая данные между двумя массивами; иногда быстрее при мелких ключах, но теряется «на месте».
- Шаг 1 как «стандартные вставки»: финальный проход — это в точности Сортировка вставками, поэтому на почти упорядоченном массиве он линеен.
- Неустойчивость и кэш: при [math]\displaystyle{ h \gt 1 }[/math] элементы прыгают через соседей (неустойчиво, хуже локальность), а финальный проход идёт подряд и хорошо ложится на кэш.
Сводная таблица сложности
| Последовательность шагов | Худший случай | Примечание |
|---|---|---|
| [math]\displaystyle{ h = 1 }[/math] (обычные вставки) | [math]\displaystyle{ \Theta(n^2) }[/math] | вставки |
| Шелл (степени 2: [math]\displaystyle{ n/2, n/4, \dots }[/math]) | [math]\displaystyle{ \Theta(n^2) }[/math] | классическая, но плохая |
| Hibbard ([math]\displaystyle{ 2^k-1 }[/math]) | [math]\displaystyle{ \Theta(n^{3/2}) }[/math] | Hibbard, 1963 |
| Knuth ([math]\displaystyle{ 3h+1 }[/math]) | [math]\displaystyle{ \Theta(n^{3/2}) }[/math] | Knuth (TAOCP, 1973) |
| Sedgewick | [math]\displaystyle{ O(n^{4/3}) }[/math] | формулы вида [math]\displaystyle{ 4^k \pm O(2^k) }[/math] |
| Pratt ([math]\displaystyle{ 2^p 3^q }[/math]) | [math]\displaystyle{ \Theta(n\log^2 n) }[/math] | Pratt (1972); много проходов, большие константы |
| Ciura (эмпирическая) | эмпирически [math]\displaystyle{ \approx n^{1.3} }[/math] | лучшая практика |
Оговорка: в отличие от mergesort, у сортировки Шелла нет единственной оценки [math]\displaystyle{ O(n\log n) }[/math] для всех шагов; сложность — свойство выбранной последовательности. Для конкретной последовательности оценки доказаны (см. источники).
Трассировка примера
a = [35, 33, 42, 10, 14, 19, 27, 44], шаги Knuth для [math]\displaystyle{ n=8 }[/math]: 4, 1 (см. рис. 4).
Проход [math]\displaystyle{ h = 4 }[/math] (подпоследовательности — индексы mod 4):
| Подпоследовательность | Стало |
|---|---|
[35, 14] |
14, 35
|
[33, 19] |
19, 33
|
[42, 27] |
27, 42
|
[10, 44] |
10, 44
|
Массив после [math]\displaystyle{ h = 4 }[/math]: [14, 19, 27, 10, 35, 33, 42, 44].
Проход [math]\displaystyle{ h = 1 }[/math] (обычные вставки):
| Шаг | Массив | Комментарий |
|---|---|---|
i = 3, элемент 10 |
[10, 14, 19, 27, 35, 33, 42, 44] |
10 сдвигает 27, 19, 14 вправо |
i = 5, элемент 33 |
[10, 14, 19, 27, 33, 35, 42, 44] |
33 встаёт перед 35 |
| конец | [10, 14, 19, 27, 33, 35, 42, 44] |
массив отсортирован |
Видно, что после крупного шага массив уже почти отсортирован — финальный проход делает мало сдвигов. Трассировка сверена с реализацией из раздела «Служебное»: код проверяет состояния после каждого шага.
Корректность и оценка сложности
Лемма Кнута (сохранение [math]\displaystyle{ h }[/math]-упорядоченности)
Утверждение. Если массив [math]\displaystyle{ h }[/math]-упорядочен, а затем выполняется [math]\displaystyle{ k }[/math]-sort для [math]\displaystyle{ k \lt h }[/math], массив остаётся [math]\displaystyle{ h }[/math]-упорядоченным.
Доказательство (идея). [math]\displaystyle{ k }[/math]-sort переставляет элементы только внутри [math]\displaystyle{ k }[/math]-подпоследовательностей, то есть сдвигает их на расстояния, кратные [math]\displaystyle{ k }[/math]. При [math]\displaystyle{ k \lt h }[/math] разбор случаев по остаткам позиций по модулю [math]\displaystyle{ k }[/math] и [math]\displaystyle{ h }[/math] показывает, что ни одно соотношение [math]\displaystyle{ a[i] \le a[i+h] }[/math] не нарушается; полное доказательство — у Кнута [2, §5.2.1]. [math]\displaystyle{ \square }[/math]
Корректность алгоритма
Индукция по проходам. Каждый [math]\displaystyle{ h }[/math]-sort корректно сортирует свои подпоследовательности (это сортировка вставками). По лемме Кнута ранее установленная [math]\displaystyle{ h' }[/math]-упорядоченность (для [math]\displaystyle{ h' \gt h }[/math]) не теряется. Последний шаг [math]\displaystyle{ h_k = 1 }[/math] делает массив [math]\displaystyle{ 1 }[/math]-упорядоченным, а это и есть полная сортировка (см. рис. 5). [math]\displaystyle{ \square }[/math]
Оценка сложности
Число проходов и их стоимость зависят от последовательности. Для последовательности Knuth ([math]\displaystyle{ 3h+1 }[/math]) доказывается [math]\displaystyle{ \Theta(n^{3/2}) }[/math]; для Hibbard — [math]\displaystyle{ \Theta(n^{3/2}) }[/math]; для Pratt — [math]\displaystyle{ \Theta(n\log^2 n) }[/math]; для Sedgewick-последовательностей — [math]\displaystyle{ O(n^{4/3}) }[/math]. Эмпирически последовательность Ciura даёт лучший результат. Общего [math]\displaystyle{ O(n\log n) }[/math] для сортировки Шелла не доказано; для отдельных последовательностей известны оценки снизу [4].
Сравнение с альтернативами
| Алгоритм | Худший | Память | Устойчив | Ниша |
|---|---|---|---|---|
| Шелл | [math]\displaystyle{ \approx n^{4/3} }[/math]…[math]\displaystyle{ n^{3/2} }[/math] (при хороших шагах) | [math]\displaystyle{ O(1) }[/math] | нет | простой код, без рекурсии, средние массивы |
| Вставками | [math]\displaystyle{ \Theta(n^2) }[/math] | [math]\displaystyle{ O(1) }[/math] | да | малые, почти отсортированные |
| Быстрая | [math]\displaystyle{ \Theta(n^2) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | нет | большие массивы, скорость |
| Слиянием | [math]\displaystyle{ O(n\log n) }[/math] | [math]\displaystyle{ O(n) }[/math] | да | устойчивость, списки |
| Timsort (план) | [math]\displaystyle{ O(n\log n) }[/math] | [math]\displaystyle{ O(n) }[/math] | да | реальные данные |
Вердикт. Нужен [math]\displaystyle{ O(n\log n) }[/math]-гарантированный и быстрый алгоритм — берите introsort/Timsort (см. рис. 6). Нужен очень простой код, [math]\displaystyle{ O(1) }[/math] памяти и нет рекурсии, а массив — умеренный — Шелл. Как замена квадратичным сортировкам в учебном/встраиваемом коде — отличный вариант.
Где применяется
Типичные применения — на рис. 7; ниже объяснено, почему в каждом случае выбран Шелл.
- Встраиваемые системы. [math]\displaystyle{ O(1) }[/math] памяти, короткий код без рекурсии, предсказуемое поведение — важны на микроконтроллерах и в прошивках [2][5].
- Исторические
qsort-реализации. В uClibc(-ng)qsortреализован как Shellsort (ssort()). Почему: экономия стека [5].
- Простые утилиты и скрипты. Когда не нужна максимальная скорость, а важны компактность и отсутствие зависимостей [3].
- Обучение. Классический пример «улучшения вставок» и зависимости сложности от параметра (последовательности шагов) [1][2].
- Средние массивы без лишней памяти. На массивах в сотни–тысячи элементов Шелл с последовательностью Ciura часто близок к [math]\displaystyle{ O(n\log n) }[/math]-алгоритмам при меньшей константе [3][6].
Историческая справка
Дональд Шелл предложил алгоритм в 1959 году (Shell, A High-Speed Sorting Procedure, CACM) — это одна из первых сортировок, показавших, что выбор шагов ускоряет вставки [7]. Идея убывающих шагов открыла целое направление анализа последовательностей:
- Hibbard (1963) — шаги [math]\displaystyle{ 2^k-1 }[/math], [math]\displaystyle{ \Theta(n^{3/2}) }[/math];
- Pratt (1972, диссертация) — шаги [math]\displaystyle{ 2^p 3^q }[/math], [math]\displaystyle{ \Theta(n\log^2 n) }[/math] (но много проходов);
- Knuth (TAOCP, 1973) — шаги [math]\displaystyle{ 3h+1 }[/math], [math]\displaystyle{ \Theta(n^{3/2}) }[/math], популярны на практике [2];
- Incerpi, Sedgewick (1985) — верхние оценки худшего случая для последовательностей Шелла;
- Sedgewick (1986) — последовательности с [math]\displaystyle{ O(n^{4/3}) }[/math]; точная формула — в «Служебном»;
- Ciura (2001) — эмпирически лучшая последовательность [6].
Шелл вошёл в учебники ([2][3]) как «мост» между элементарными квадратичными сортировками и [math]\displaystyle{ O(n\log n) }[/math]-алгоритмами.
Типичные ошибки и подводные камни
- Отсутствие шага [math]\displaystyle{ h = 1 }[/math]. Без него массив не отсортируется полностью.
- Плохая последовательность (степени двойки). Даёт [math]\displaystyle{ \Theta(n^2) }[/math] — худший случай классической версии.
- Ожидание устойчивости. При [math]\displaystyle{ h \gt 1 }[/math] равные элементы переставляются — сортировка Шелла неустойчива.
- Ошибки индексации при сдвиге на [math]\displaystyle{ h }[/math]. Классика:
j ≥ 0иa[j + h] = a[j], а неa[j+1]. - Много маленьких шагов. Например, последовательность «все степени 2» или слишком длинная — растут накладные расходы.
- Pratt «в лоб». Много проходов ([math]\displaystyle{ O(\log^2 n) }[/math]), большие константы; на практике проигрывает.
- Смешение с вставками. Обычные вставки — это Шелл с одной последовательностью
[1]. - Применение к большим массивам без нужды. [math]\displaystyle{ O(n\log n) }[/math]-алгоритмы быстрее и предсказуемее.
- Дорогие перемещения. При [math]\displaystyle{ h \gt 1 }[/math] кэш-поведение хуже, чем у финального прохода.
- Забыть про
long long/тип шага. Для больших [math]\displaystyle{ n }[/math] шаги могут переполниться приint.
Задачи для практики
- Базовая реализация. Реализуйте Shellsort с последовательностью Knuth. Подсказка: цикл по шагам, внутри — вставки со сдвигом.
- Инвариант. Проверьте, что после каждого прохода массив [math]\displaystyle{ h }[/math]-упорядочен. Подсказка: степень [math]\displaystyle{ h }[/math]-упорядоченности.
- Последовательности. Сравните число сравнений для шагов степени 2, Hibbard, Knuth, Ciura на одном массиве. Подсказка: счётчики сравнений/сдвигов.
- Худший вход. Для шагов [math]\displaystyle{ n/2, n/4, \dots }[/math] постройте вход, дающий [math]\displaystyle{ \Theta(n^2) }[/math]. Подсказка: рассмотрите элементы на позициях, остающихся «далеко».
- Лемма Кнута. Докажите частный случай: 2-упорядоченный массив после 1-sort остаётся 2-упорядоченным. Подсказка: разбор расстояний.
- Двухмассивный Шелл. Реализуйте вариант с буфером и сравните по времени на маленьких ключах. Подсказка: перекладывание между массивами.
- Shellsort vs вставки. Покажите на бенчмарке, во сколько раз Шелл быстрее вставок при [math]\displaystyle{ n = 10^4 }[/math]. Подсказка: случайные данные.
- Ciura для больших n. Продолжите последовательность Ciura умножением на 2.25 и оцените поведение. Подсказка: следите за ростом шагов.
Ответы и оценки сложности.
- Сравнений [math]\displaystyle{ O(n\cdot k) }[/math] для [math]\displaystyle{ k }[/math] проходов, память [math]\displaystyle{ O(1) }[/math]; корректность — индукция по шагам.
- После каждого [math]\displaystyle{ h }[/math]-sort массив [math]\displaystyle{ h }[/math]-упорядочен; это проверяется проходом по каждой подпоследовательности.
- На случайных данных меньше всего сравнений обычно у Ciura; степени двойки — худший вариант.
- Степени двойки дают [math]\displaystyle{ \Theta(n^2) }[/math]; вход строится из элементов, которые после крупных шагов остаются «далеко».
- 2-упорядоченность сохраняется при 1-sort — частный случай леммы Кнута.
- Двухмассивный вариант требует [math]\displaystyle{ O(n) }[/math] дополнительной памяти.
- Шелл с Ciura обычно даёт заметный выигрыш по сравнениям/перемещениям, но зависит от данных.
- Продолжение Ciura эмпирическое: рост шагов ≈2.25, гарантии [math]\displaystyle{ O(n\log n) }[/math] нет.
Связанные темы
- Сортировка вставками — базовый алгоритм; Шелл — его обобщение.
- Сортировка выбором — другой элементарный алгоритм с минимумом записей.
- Сортировки (план) — обзор и нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math].
- Быстрая сортировка — современная альтернатива для больших массивов.
- Сортировка слиянием — [math]\displaystyle{ O(n\log n) }[/math] с устойчивостью.
- Timsort (план) — использует вставки (не Шелл) на коротких отрезках.
- Асимптотическая сложность (план) — оценки, зависящие от параметра.
Источники
- Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 2 (сортировки, вставки как основа).
- Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.1 (Shellsort; последовательности шагов; анализ).
- Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — §2.1 (Elementary Sorts, Shellsort).
- Sedgewick R. Analysis of Shellsort and Related Algorithms // ESA. — 1996 (обзор оценок).
- Wikipedia: Shellsort. URL: https://en.wikipedia.org/wiki/Shellsort.
- Ciura M. Best Increments for the Average Case of Shellsort // FCT. — 2001.
- Shell D. L. A High-Speed Sorting Procedure // CACM. — 1959. — Vol. 2, № 7.
- Pratt V. R. Shellsort and Sorting Networks. — PhD thesis, Stanford, 1972.