Сортировка Шелла

Сортировка Шелла (англ. Shellsort) - алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками.

Алгоритм

Каждый проход в алгоритме характеризуется смещением [math]h[/math], таким, что сортируются элементы отстающие друг от друга на [math]h[/math] позиций. Шелл предлагал использовать [math]h_t = N/2[/math], [math]h_{t-1} = h_t/2[/math], ..., [math]h_0 = 1[/math], здесь [math]t = \left \lfloor log_2 {N} \right \rfloor - 1[/math]. Возможны и другие смещения, но [math]h_0 = 1[/math] всегда.

• Начало.
• Шаг 0. [math]i = t[/math].
• Шаг 1. Разобьем массив на списки элементов отстающих друг от друга на [math]h_i[/math], таких списков будет [math]h_i[/math].
• Шаг 2. Отсортируем элементы каждого списка сортировкой вставками.
• Шаг 3. Объединим списки обратно в массив. Уменьшим [math]i[/math], если [math]i[/math] неотрицательно вернемся к шагу 1.
• Конец.

Пример

Возьмем массив [math]A= \{[/math] 56, 43, 12, 78, 42, 93, 16, 55 [math]\} [/math]. И смещения предложенные Шеллом.

До	После	Описание шага
Шаг 1 [math]i = t = 2[/math]
56, 43, 12, 78, 42, 93, 16, 55	[math]\{[/math] 56, 42 [math]\} [/math] [math]\{[/math] 43, 93 [math]\} [/math] [math]\{[/math] 12, 16 [math]\} [/math] [math]\{[/math] 78, 55 [math]\} [/math]	Разбили массив на 4 списка.
Шаг 2
[math]\{[/math] 56, 42 [math]\} [/math] [math]\{[/math] 43, 93 [math]\} [/math] [math]\{[/math] 12, 16 [math]\} [/math] [math]\{[/math] 78, 55 [math]\} [/math]	[math]\{[/math] 42, 56 [math]\} [/math] [math]\{[/math] 43, 93 [math]\} [/math] [math]\{[/math] 12, 16 [math]\} [/math] [math]\{[/math] 55, 78 [math]\} [/math]	Отсортировали элементы списков сортировкой вставками, количество обменов 2.
Шаг 3
[math]\{[/math] 42, 56 [math]\} [/math] [math]\{[/math] 43, 93 [math]\} [/math] [math]\{[/math] 12, 16 [math]\} [/math] [math]\{[/math] 55, 78 [math]\} [/math]	42, 43, 12, 55, 56, 93, 16, 78	Объединили списки в массив. Уменьшаем [math]i[/math] на 1, [math]i \geqslant 0[/math]. Перейдем к шагу 1.
Шаг 1 [math]i = 1[/math]
42, 43, 12, 55, 56, 93, 16, 78	[math]\{[/math] 42, 12, 56, 16 [math]\} [/math] [math]\{[/math] 43, 55, 93, 78 [math]\} [/math]	Разбили массив на 2 списка.
Шаг 2
[math]\{[/math] 42, 12, 56, 16 [math]\} [/math] [math]\{[/math] 43, 55, 93, 78 [math]\} [/math]	[math]\{[/math] 12, 16, 42, 56 [math]\} [/math] [math]\{[/math] 43, 55, 78, 93 [math]\} [/math]	Отсортировали элементы списков сортировкой вставками, количество обменов 4.
Шаг 3
[math]\{[/math] 12, 16, 42, 56 [math]\} [/math] [math]\{[/math] 43, 55, 78, 93 [math]\} [/math]	12, 43, 16, 55, 42, 78, 56, 93	Объединили списки в массив. Уменьшаем [math]i[/math] на 1, [math]i \geqslant 0[/math]. Перейдем к шагу 1.
Шаг 1 [math]i = 0[/math]
42, 43, 12, 55, 56, 93, 16, 78	[math]\{[/math] 42, 43, 12, 55, 56, 93, 16, 78 [math]\} [/math]	Разбили массив на 1 список.
Шаг 2
[math]\{[/math] 42, 43, 12, 55, 56, 93, 16, 78 [math]\} [/math]	[math]\{[/math] 12, 16, 42, 43, 55, 56, 78, 93 [math]\} [/math]	Отсортировали элементы списков сортировкой вставками, количество обменов 7.
Шаг 3
[math]\{[/math] 12, 16, 42, 43, 55, 56, 78, 93 [math]\} [/math]	12, 16, 42, 43, 55, 56, 78, 93	Объединили списки в массив. Уменьшаем [math]i[/math] на 1, [math]i\lt 0[/math].

Анализ метода Шелла

Понятно, что сложность алгоритма зависит от оптимальности выбора набора [math]h_i[/math]. Массив где для ∀ [math]i[/math] верно [math] a_i \leqslant a_{i+h}[/math], назовем [math]h[/math] упорядоченным.

Теорема (Д.Х. Ханту):

Среднее число инверсий в [math]h[/math] упорядоченной перестановке множества [math]\{[/math] 1, 2, ..., [math]n \}[/math] равно [math] f(n,h) = \dfrac{2^{2q-1}q!q!}{(2q+1)!}(\binom{h}{2}q(q+1) + \binom{r}{2}(q+1)-1/2\binom{h-r}{2}q) [/math], где [math]q = \frac{n}{h} [/math] и [math] r = n\,\bmod\,h [/math]

Следующая лемма является следствием теоремы выше.

Лемма:

Если последовательность смещений [math]h_{t-1}, ..., h_1, h_0[/math], удовлетворяют условию [math] h_{s+1}\,\bmod\,h_s = 0[/math] при [math]t-1\gt s\geqslant0[/math], то среднее число операций равно [math]D = \sum_{t-1\gt s\geqslant0}^{} (r_sf(q_s+1,h_{s+1}/h_s) + (h_s - r_s)f(q_s,h_{s+1}/h_s))[/math], где [math]r_s=N\,\bmod\,h_s[/math], [math]q_s = \frac{N}{h_s}[/math], [math] h_t = Nh_{t-1}[/math], а функция [math]f[/math] определяется формулой из теоремы.

Доказательство данной теоремы и леммы можно найти в книге Д. Кнут Искусство программирования, том 3. Сортировка и поиск. (5.2.1)

В первом приближении функция [math]f(n,h)[/math] равна [math] (\sqrt{\pi}/8)n^{3/2}h^{1/2}[/math]. Следовательно [math]D[/math] для двух проходов будет примерно пропорционально [math]2N^2/h+\sqrt{\pi N^3h}[/math]. По этому наилучшее значение [math]h[/math] равно приблизительно [math]\sqrt[3]{16N/ {\pi}} \approx 1.72\sqrt[3]{N}[/math], при таком выборе [math]h[/math] среднее время сортировка пропорционально [math]N^{5/3}[/math].

Таким образом, применяя метод Шелла и используя всего 2 прохода, можно сократить время по сравнению с методом простых вставок с [math]O(N^2)[/math] до [math]O(N^{1.(6)})[/math].

Используя приведенные выше формулы порог [math]N^{1.5}[/math] преодолеть невозможно, но если убрать ограничение [math] h_{s+1}\,\bmod\,h_s = 0[/math] его можно преодолеть.

Теорема (А.А. Папернов, Г.В. Стасевич):

Если [math]h_s=2^{s+1}-1[/math] при [math]0 \leqslant s \lt t = \left \lfloor ln N \right \rfloor[/math], то время сортировки есть [math]O(N^{3/2})[/math].

Доказательство:

[math]\triangleright[/math]

Достаточно найти оценку числа перезаписей [math]B_s[/math] на [math]s[/math] проходе, такую, что бы [math]B_{t-1}+...+B_0=O(N^{3/2})[/math]. Для первых [math]t/2[/math] проходов при [math] t\gt s\geqslant t/2[/math] можно воспользоваться оценкой [math]B_s=O(h_s(N/h_s)^2)[/math], а для последующих проходов [math]B_s=O(Nh_{s+2}h_{s+1}/h_s)[/math], следовательно [math]B_{t-1}+...+B_0=O(N(2+2^2+...+2^{t/2}+2^{t/2}+...+2^2+2))=O(N^{3/2})[/math].

[math]\triangleleft[/math]

Важно, что эта теорема дает оценку времени выполнения алгоритма в худшем случае.

Дальнейшее улучшение было получено Волганом Праттом. Если все смещения при сортировке выбираются из множества чисел вида [math]2^p3^q[/math], меньших [math]N[/math], то время выполнения алгоритма будет порядка [math]N(logN)^2[/math].

Смотри также

• Сортировка выбором
• Быстрая сортировка

Литература

• Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — 824 с. — ISBN 5-8459-0082-4

Ссылки

Сортировка Шелла в русской википедии