60
правок
Изменения
Нет описания правки
'''''Сортировка Шелла''''' (англ. Shellsort) - — алгоритм сортировки, являющийся усовершенствованным вариантом [[Сортировка вставками|сортировки вставками]].
==Алгоритм==
Каждый проход в алгоритме характеризуется смещением <tex>h_i</tex>, таким, что сортируются элементы отстающие друг от друга на <tex>h_i</tex> позиций.
Шелл предлагал использовать <tex>h_t = N/2</tex>, <tex>h_{t-1} = h_t/2</tex>, ...<tex>\ldots</tex> , <tex>h_0 = 1</tex>. Возможны и другие смещения, но <tex>h_0 = 1</tex> всегда.
* Начало.
* '''Шаг 1.''' Разобьем массив на списки элементов, отстающих друг от друга на <tex>h_i</tex>. Таких списков будет <tex>h_i</tex>.
* '''Шаг 2.''' Отсортируем элементы каждого списка [[Сортировка вставками|сортировкой вставками]].
* '''Шаг 3.''' Объединим списки обратно в массив. Уменьшим <tex>i</tex>. Если <tex>i</tex> неотрицательно - — вернемся к шагу 1
* Конец.
|author= Д.Х. Ханту
|statement=
Среднее число инверсий в <tex>h</tex> упорядоченной перестановке множества <tex>\{</tex> ''1, 2, ...<tex>\ldots</tex> , <tex>n \}</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>
|about=
|statement=
Если последовательность смещений <tex>h_{t-1}, ...\ldots , 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> определяется формулой из теоремы.
|author= А.А. Папернов, Г.В. Стасевич
|statement=
Если <tex>h_s=2^{s+1}-1</tex> при <tex>0 \leqslant s < t = \left \lfloor \ln N \right \rfloor</tex>, то время сортировки есть <tex>O(N^{3/2})</tex>.
|proof=
Достаточно найти оценку числа перезаписей <tex>B_s</tex> на <tex>s</tex> проходе, такую, что бы <tex>B_{t-1}+...\ldots +B_0=O(N^{3/2})</tex>. Для первых <tex>t/2</tex> проходов при <tex> t>s\geqslant t/2</tex> можно воспользоваться оценкой <tex>B_s=O(h_s(N/h_s)^2)</tex>, а для последующих проходов <tex>B_s=O(Nh_{s+2}h_{s+1}/h_s)</tex>, следовательно <tex>B_{t-1}+...\ldots +B_0=O(N(2+2^2+...\ldots +2^{t/2}+2^{t/2}+...\ldots +2^2+2))=O(N^{3/2})</tex>.
}}
Важно, что эта теорема дает оценку времени выполнения алгоритма в худшем случае.
Дальнейшее улучшение было получено Волганом Праттом. Если все смещения при сортировке выбираются из множества чисел вида <tex>2^p3^q</tex>, меньших <tex>N</tex>, то время выполнения алгоритма будет порядка <tex>O(N\log^2{N})</tex>.
== Смотри См. также ==
* [[Сортировка выбором]]
* [[Сортировка вставками]]
* [[Быстрая сортировка]]
== Литература Источники информации ==* Дональд Кнут — Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — 824 с. — ISBN 5-8459-0082-4 == Ссылки == * [http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%A8%D0%B5%D0%BB%D0%BB%D0%B0 Сортировка Шелла в русской википедии— Википедия]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: СортировкаСортировки]]
