Изменения
Нет описания правки
|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"| ''42, 43, 12, 55, 56, 93, 16, 78''
|style="background-color:#FFF;padding:2px 10px"| Объединили списки в массив. Уменьшаем <tex>i</tex> на 1, . <tex>i \geqslant 0</tex>. Перейдем , перейдем к шагу 1.
|-
| ''Шаг 1'' <tex>i = 1</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"| ''12, 43, 16, 55, 42, 78, 56, 93''
|style="background-color:#FFF;padding:2px 10px"| Объединили списки в массив. Уменьшаем <tex>i</tex> на 1, . <tex>i \geqslant 0</tex>. Перейдем , перейдем к шагу 1.
|-
| ''Шаг 1'' <tex>i = 0</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"| ''12, 16, 42, 43, 55, 56, 78, 93''
|style="background-color:#FFF;padding:2px 10px"| Объединили списки в массив. Уменьшаем <tex>i</tex> на 1, . <tex>i<0</tex>.
|}
==Анализ метода Шелла==
Понятно, что сложность алгоритма зависит от оптимальности выбора набора <tex>h_i</tex>.
Массив , где для любого <tex>i</tex> верно <tex> a_i \leqslant a_{i+h}</tex>, назовем <tex>h</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>.
Важно, что эта теорема дает оценку времени выполнения алгоритма в худшем случае.
Дальнейшее улучшение было получено Волганом Праттом. Если все смещения при сортировке выбираются из множества чисел вида <tex>2^p3^q</tex>, меньших <tex>N</tex>, то время выполнения алгоритма будет порядка <tex>О(Nlog^2{N})</tex>.
== Смотри также ==
