Изменения
Нет описания правки
==Алгоритм==
Каждый проход в алгоритме характеризуется смещением <tex>h</tex>, таким, что сортируются элементы отстающие друг от друга на <tex>h</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> всегда.
* Начало.
<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
|about=
|statement=
Если последовательность смещений <tex>h_{t-1}, ..., h_1, h_0</tex>, удовлетворяют условию <tex> h_{s+1}\,\bmod\,h_s = 0</tex> при <tex>t-1>s\geqslant0</tex>, то среднее число операций равно
<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> определяется формулой из теоремы.
}}
Доказательство данной теоремы и леммы можно найти в книге Д. Кнут Искусство программирования, том 3. Сортировка и поиск. (5.2.1)
В первом приближении функция <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>.
