Изменения
Нет описания правки
==Алгоритм==
Каждый проход в алгоритме характеризуется смещением <tex>hh_i</tex>, таким, что сортируются элементы отстающие друг от друга на <tex>hh_i</tex> позиций.Шелл предлагал использовать <tex>h_t = N/2</tex>, <tex>h_{t-1} = h_t/2</tex>, ..., <tex>h_0 = 1</tex>, здесь <tex>t = \left \lfloor log_2 {N} \right \rfloor - 1</tex>количество проходов минус один. Возможны и другие смещения, но <tex>h_0 = 1</tex> всегда.
* Начало.
* '''Шаг 0.''' <tex>i = t</tex>.
* '''Шаг 1.''' Разобьем массив на списки элементов , отстающих друг от друга на <tex>h_i</tex>, таких . Таких списков будет <tex>h_i</tex>.
* '''Шаг 2.''' Отсортируем элементы каждого списка [[Сортировка вставками|сортировкой вставками]].
* '''Шаг 3.''' Объединим списки обратно в массив. Уменьшим <tex>i</tex>, если <tex>i</tex> неотрицательно вернемся к шагу 1.
==Пример==
Возьмем массив <tex>A= \{</tex> ''56, 43, 12, 78, 42, 93, 16, 55'' <tex>\} </tex>. И и смещения предложенные Шеллом.
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| До
|style="background-color:#FFF;padding:2px 10px"| <tex>\{</tex> ''56, 42'' <tex>\} </tex> <tex>\{</tex> ''43, 93'' <tex>\} </tex> <tex>\{</tex> ''12, 16'' <tex>\} </tex> <tex>\{</tex> ''78, 55'' <tex>\} </tex>
|style="background-color:#FFF;padding:2px 10px"| <tex>\{</tex> ''42, 56'' <tex>\} </tex> <tex>\{</tex> ''43, 93'' <tex>\} </tex> <tex>\{</tex> ''12, 16'' <tex>\} </tex> <tex>\{</tex> ''55, 78'' <tex>\} </tex>
|style="background-color:#FFF;padding:2px 10px"| Отсортировали элементы списков сортировкой вставками, количество . Количество обменов 2.
|-
| ''Шаг 3''
|style="background-color:#FFF;padding:2px 10px"| <tex>\{</tex> ''42, 12, 56, 16'' <tex>\} </tex> <tex>\{</tex> ''43, 55, 93, 78'' <tex>\} </tex>
|style="background-color:#FFF;padding:2px 10px"| <tex>\{</tex> ''12, 16, 42, 56'' <tex>\} </tex> <tex>\{</tex> ''43, 55, 78, 93'' <tex>\} </tex>
|style="background-color:#FFF;padding:2px 10px"| Отсортировали элементы списков сортировкой вставками, количество . Количество обменов 4.
|-
| ''Шаг 3''
|style="background-color:#FFF;padding:2px 10px"| <tex>\{</tex> ''42, 43, 12, 55, 56, 93, 16, 78'' <tex>\} </tex>
|style="background-color:#FFF;padding:2px 10px"| <tex>\{</tex> ''12, 16, 42, 43, 55, 56, 78, 93'' <tex>\} </tex>
|style="background-color:#FFF;padding:2px 10px"| Отсортировали элементы списков сортировкой вставками, количество . Количество обменов 7.
|-
| ''Шаг 3''
==Анализ метода Шелла==
Понятно, что сложность алгоритма зависит от оптимальности выбора набора <tex>h_i</tex>.
Массив где для ∀ любого <tex>i</tex> верно <tex> a_i \leqslant a_{i+h}</tex>, назовем <tex>h</tex> упорядоченным.
{{Теорема
<tex> 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) </tex>, где <tex>q = \frac{n}{h} </tex> и <tex> r = n\,\bmod\,h </tex>
}}
Следующая лемма является следствием теоремы выше.
{{Лемма
|id=sledstvie1
<tex>D = \sum_{t-1>s\geqslant0}^{} (r_sf(q_s+1,h_{s+1}/h_s) + (h_s - r_s)f(q_s,h_{s+1}/h_s))</tex>, где <tex>r_s=N\,\bmod\,h_s</tex>, <tex>q_s = \frac{N}{h_s}</tex>, <tex> h_t = Nh_{t-1}</tex>, а функция <tex>f</tex> определяется формулой из теоремы.
}}
Доказательство данных теоремы и леммы изложено в первой книге предложенных к прочтению. В первом приближении функция <tex>f(n,h)</tex> равна <tex> (\sqrt{\pi}/8)n^{3/2}h^{1/2}</tex>. Следовательно <tex>D</tex> для двух проходов будет примерно пропорционально <tex>2N^2/h+\sqrt{\pi N^3h}</tex>. По этому Поэтому наилучшее значение <tex>h</tex> равно приблизительно <tex>\sqrt[3]{16N/ {\pi}} \approx 1.72\sqrt[3]{N}</tex>, при таком выборе <tex>h</tex> среднее время сортировка пропорционально <tex>N^{5/3}</tex>.
Таким образом, применяя метод Шелла и используя всего 2 прохода, можно сократить время по сравнению с методом простых вставок с <tex>O(N^2)</tex> до <tex>O(N^{1.(6)})</tex>.
Используя приведенные выше формулы , порог <tex>N^{1.5}</tex> преодолеть невозможно, но если убрать ограничение <tex> h_{s+1}\,\bmod\,h_s = 0</tex> его можно преодолеть.
{{Теорема
Важно, что эта теорема дает оценку времени выполнения алгоритма в худшем случае.
Дальнейшее улучшение было получено Волганом Праттом. Если все смещения при сортировке выбираются из множества чисел вида <tex>2^p3^q</tex>, меньших <tex>N</tex>, то время выполнения алгоритма будет порядка <tex>N(logN)Nlog^2{N}</tex>.
== Смотри также ==
* [[Сортировка выбором]]
* [[Сортировка вставками]]
* [[Быстрая сортировка]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка ]]
