Сортировка Шелла — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Орфография)
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 5 участников)
Строка 1: Строка 1:
'''''Сортировка Шелла''''' (англ. Shellsort) - алгоритм сортировки, являющийся усовершенствованным вариантом [[Сортировка вставками|сортировки вставками]].  
+
'''''Сортировка Шелла''''' (англ. Shellsort) алгоритм сортировки, являющийся усовершенствованным вариантом [[Сортировка вставками|сортировки вставками]].  
  
 
==Алгоритм==
 
==Алгоритм==
Каждый проход в алгоритме характеризуется смещением <tex>h</tex>, таким, что сортируются элементы отстающие друг от друга на <tex>h</tex> позиций.
+
Каждый проход в алгоритме характеризуется смещением <tex>h_i</tex>, таким, что сортируются элементы отстающие друг от друга на <tex>h_i</tex> позиций.
Шелл предлагал использовать <tex>h_t = N/2</tex>, <tex>h_{t-1} = h_t/2</tex>, ..., <tex>h_0 = 1</tex>. Возможны и другие смещения, но <tex>h_0 = 1</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> всегда.
  
 
* Начало.
 
* Начало.
 
* '''Шаг 0.''' <tex>i = t</tex>.
 
* '''Шаг 0.''' <tex>i = t</tex>.
* '''Шаг 1.''' Разобьем массив на списки элементов отстающих друг от друга на <tex>h_i</tex>, таких списков будет <tex>h_i</tex>.
+
* '''Шаг 1.''' Разобьем массив на списки элементов, отстающих друг от друга на <tex>h_i</tex>. Таких списков будет <tex>h_i</tex>.
 
* '''Шаг 2.''' Отсортируем элементы каждого списка [[Сортировка вставками|сортировкой вставками]].
 
* '''Шаг 2.''' Отсортируем элементы каждого списка [[Сортировка вставками|сортировкой вставками]].
* '''Шаг 3.''' Объединим списки обратно в массив. Уменьшим <tex>i</tex>, если <tex>i</tex> неотрицательно вернемся к шагу 1.
+
* '''Шаг 3.''' Объединим списки обратно в массив. Уменьшим <tex>i</tex>. Если <tex>i</tex> неотрицательно вернемся к шагу 1
 
* Конец.
 
* Конец.
  
 
==Пример==
 
==Пример==
Возьмем массив <tex>A= \{</tex> ''56, 43, 12, 78, 42, 93, 16, 55'' <tex>\} </tex>. И смещения предложенные Шеллом.
+
Возьмем массив <tex>A= \{</tex> ''56, 43, 12, 78, 42, 93, 16, 55'' <tex>\} </tex> и смещения предложенные Шеллом.
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
 
!style="background-color:#EEE"| До
 
!style="background-color:#EEE"| До
Строка 29: Строка 29:
 
|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> ''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"| <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.
+
|style="background-color:#FFF;padding:2px 10px"| Отсортировали элементы списков сортировкой вставками. Количество обменов 2.
 
|-
 
|-
 
| ''Шаг 3''
 
| ''Шаг 3''
Строка 35: Строка 35:
 
|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"| <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"| ''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.
+
|style="background-color:#FFF;padding:2px 10px"| Объединили списки в массив. Уменьшаем <tex>i</tex> на 1. <tex>i \geqslant 0</tex>, перейдем к шагу 1.
 
|-
 
|-
 
| ''Шаг 1'' <tex>i = 1</tex>
 
| ''Шаг 1'' <tex>i = 1</tex>
Строка 47: Строка 47:
 
|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> ''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"| <tex>\{</tex> ''12, 16, 42, 56'' <tex>\} </tex> <tex>\{</tex> ''43, 55, 78, 93'' <tex>\} </tex>
|style="background-color:#FFF;padding:2px 10px"| Отсортировали элементы списков сортировкой вставками, количество обменов 4.
+
|style="background-color:#FFF;padding:2px 10px"| Отсортировали элементы списков сортировкой вставками. Количество обменов 4.
 
|-
 
|-
 
| ''Шаг 3''
 
| ''Шаг 3''
Строка 53: Строка 53:
 
|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"| <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"| ''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.
+
|style="background-color:#FFF;padding:2px 10px"| Объединили списки в массив. Уменьшаем <tex>i</tex> на 1. <tex>i \geqslant 0</tex>, перейдем к шагу 1.
 
|-
 
|-
 
| ''Шаг 1'' <tex>i = 0</tex>
 
| ''Шаг 1'' <tex>i = 0</tex>
Строка 65: Строка 65:
 
|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> ''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"| <tex>\{</tex> ''12, 16, 42, 43, 55, 56, 78, 93'' <tex>\} </tex>
|style="background-color:#FFF;padding:2px 10px"| Отсортировали элементы списков сортировкой вставками, количество обменов 7.
+
|style="background-color:#FFF;padding:2px 10px"| Отсортировали элементы списков сортировкой вставками. Количество обменов 7.
 
|-
 
|-
 
| ''Шаг 3''
 
| ''Шаг 3''
Строка 71: Строка 71:
 
|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"| <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"| ''12, 16, 42, 43, 55, 56, 78, 93''
|style="background-color:#FFF;padding:2px 10px"| Объединили списки в массив. Уменьшаем <tex>i</tex> на 1, <tex>i<0</tex>.
+
|style="background-color:#FFF;padding:2px 10px"| Объединили списки в массив. Уменьшаем <tex>i</tex> на 1. <tex>i<0</tex>.
 
|}
 
|}
 
==Анализ метода Шелла==
 
==Анализ метода Шелла==
 
Понятно, что сложность алгоритма зависит от оптимальности выбора набора <tex>h_i</tex>.
 
Понятно, что сложность алгоритма зависит от оптимальности выбора набора <tex>h_i</tex>.
Массив где для <tex>i</tex> верно <tex> a_i \leqslant a_{i+h}</tex>, назовем <tex>h</tex> упорядоченным.
+
Массив, где для любого <tex>i</tex> верно <tex> a_i \leqslant a_{i+h}</tex>, назовем <tex>h</tex> упорядоченным.
 +
 
  
 
{{Теорема
 
{{Теорема
 
|id=teotema1
 
|id=teotema1
|about=1
+
|author= Д.Х. Ханту
 
|statement=
 
|statement=
Среднее число инверсий в <tex>h</tex> упорядоченной перестановке множества <tex>\{</tex> ''1, 2, ..., <tex>n \}</tex> равно
+
Среднее число инверсий в <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>
 
<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
 
|id=sledstvie1
|about=1
+
|about=
 
|statement=
 
|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>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> определяется формулой из теоремы.
 
<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> определяется формулой из теоремы.
Строка 98: Строка 99:
  
  
В первом приближении функция <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>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>.
 
Таким образом, применяя метод Шелла и используя всего 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>N^{1.5}</tex> преодолеть невозможно, но если убрать ограничение <tex> h_{s+1}\,\bmod\,h_s = 0</tex> его можно преодолеть.
 +
 
  
 
{{Теорема
 
{{Теорема
 
|id=teotema2
 
|id=teotema2
|about=
+
|author= А.А. Папернов, Г.В. Стасевич
 
|statement=
 
|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>.
+
Если <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=
 
|proof=
Достаточно найти оценку числа перезаписей <tex>B_s</tex> на <tex>s</tex> проходе, такую, что бы <tex>B_{t-1}+...+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}+...+B_0=O(N(2+2^2+...+2^{t/2}+2^{t/2}+...+2^2+2))=O(N^{3/2})</tex>.
+
Достаточно найти оценку числа перезаписей <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>N(logN)^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
+
* Дональд Кнут Искусство программирования, том 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 Сортировка Шелла — Википедия]
== Ссылки ==
 
[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 Сортировка Шелла в русской википедии]
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
+
[[Категория: Сортировка]]
[[Категория: Сортировка ]]
+
[[Категория: Сортировка на сравнениях]]

Текущая версия на 19:26, 4 сентября 2022

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

Алгоритм

Каждый проход в алгоритме характеризуется смещением [math]h_i[/math], таким, что сортируются элементы отстающие друг от друга на [math]h_i[/math] позиций. Шелл предлагал использовать [math]h_t = N/2[/math], [math]h_{t-1} = h_t/2[/math], [math]\ldots[/math] , [math]h_0 = 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]\ldots[/math] , [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}, \ldots , 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] определяется формулой из теоремы.


Доказательство данных теоремы и леммы изложено в книге, предложенной к прочтению.

В первом приближении функция [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}+\ldots +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}+\ldots +B_0=O(N(2+2^2+\ldots +2^{t/2}+2^{t/2}+\ldots +2^2+2))=O(N^{3/2})[/math].
[math]\triangleleft[/math]

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

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

См. также

Источники информации

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