Сортировка Шелла - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:26:02Z

rollbackEdits.php mass rollback

103.251.167.21 в 04:59, 1 сентября 2022

2022-09-01T04:59:55Z

Artem Ivanov в 14:22, 2 января 2016

2016-01-02T14:22:47Z

Artem Ivanov в 12:27, 30 декабря 2015

2015-12-30T12:27:02Z

94.25.229.87 в 10:56, 12 июня 2013

2013-06-12T10:56:35Z

94.25.229.55: /* Алгоритм */

2013-05-23T20:39:18Z

‎Алгоритм

94.25.229.55: /* Анализ метода Шелла */

2013-05-23T20:34:02Z

‎Анализ метода Шелла

94.25.229.55 в 20:33, 23 мая 2013

2013-05-23T20:33:17Z

94.25.229.55 в 20:51, 22 мая 2013

2013-05-22T20:51:44Z

94.25.229.55 в 20:42, 22 мая 2013

2013-05-22T20:42:10Z

← Предыдущая		Версия 16:26, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''''Сортировка Шелла''''' (англ. Shellsort) — алгоритм сортировки, являющийся усовершенствованным вариантом [[Сортировка вставками\|сортировки вставками]].		'''''Сортировка Шелла''''' (англ. Shellsort) — алгоритм сортировки, являющийся усовершенствованным вариантом [[Сортировка вставками\|сортировки вставками]].

← Предыдущая		Версия 04:59, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''''Сортировка Шелла''''' (англ. Shellsort) — алгоритм сортировки, являющийся усовершенствованным вариантом [[Сортировка вставками\|сортировки вставками]].		'''''Сортировка Шелла''''' (англ. Shellsort) — алгоритм сортировки, являющийся усовершенствованным вариантом [[Сортировка вставками\|сортировки вставками]].

@@ Строка 130: / Строка 130: @@
 [[Категория: Дискретная математика и алгоритмы]]
+[[Категория: Сортировка]]
-[[Категория: Сортировки]]
+[[Категория: Сортировка на сравнениях]]

@@ Строка 1: / Строка 1: @@
-'''''Сортировка Шелла''''' (англ. Shellsort) - алгоритм сортировки, являющийся усовершенствованным вариантом [[Сортировка вставками|сортировки вставками]].
+'''''Сортировка Шелла''''' (англ. Shellsort) — алгоритм сортировки, являющийся усовершенствованным вариантом [[Сортировка вставками|сортировки вставками]].
 ==Алгоритм==
 Каждый проход в алгоритме характеризуется смещением <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> всегда.
 * Начало.
@@ Строка 9: / Строка 9: @@
 * '''Шаг 1.''' Разобьем массив на списки элементов, отстающих друг от друга на <tex>h_i</tex>. Таких списков будет <tex>h_i</tex>.
 * '''Шаг 2.''' Отсортируем элементы каждого списка [[Сортировка вставками|сортировкой вставками]].
-* '''Шаг 3.''' Объединим списки обратно в массив. Уменьшим <tex>i</tex>. Если <tex>i</tex> неотрицательно - вернемся к шагу 1
+* '''Шаг 3.''' Объединим списки обратно в массив. Уменьшим <tex>i</tex>. Если <tex>i</tex> неотрицательно — вернемся к шагу 1
 * Конец.
@@ Строка 82: / Строка 82: @@
 |author= Д.Х. Ханту
 |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>
@@ Строка 93: / Строка 93: @@
 |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>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> определяется формулой из теоремы.
@@ Строка 112: / Строка 112: @@
 |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>.
+Если <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}+...+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>.
 }}
 Важно, что эта теорема дает оценку времени выполнения алгоритма в худшем случае.
@@ Строка 120: / Строка 120: @@
 Дальнейшее улучшение было получено Волганом Праттом. Если все смещения при сортировке выбираются из множества чисел вида <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 Сортировка Шелла — Википедия]
 [[Категория: Дискретная математика и алгоритмы]]
-[[Категория: Сортировка]]
+[[Категория: Сортировки]]

@@ Строка 118: / Строка 118: @@
 Важно, что эта теорема дает оценку времени выполнения алгоритма в худшем случае.
-Дальнейшее улучшение было получено Волганом Праттом. Если все смещения при сортировке выбираются из множества чисел вида <tex>2^p3^q</tex>, меньших <tex>N</tex>, то время выполнения алгоритма будет порядка <tex>O(Nlog^2{N})</tex>.
+Дальнейшее улучшение было получено Волганом Праттом. Если все смещения при сортировке выбираются из множества чисел вида <tex>2^p3^q</tex>, меньших <tex>N</tex>, то время выполнения алгоритма будет порядка <tex>O(N\log^2{N})</tex>.
 == Смотри также ==

@@ Строка 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"| ''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>
@@ Строка 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"| ''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>
@@ Строка 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"| ''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>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> упорядоченным.
@@ Строка 99: / Строка 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>.
@@ Строка 118: / Строка 118: @@
 Важно, что эта теорема дает оценку времени выполнения алгоритма в худшем случае.
-Дальнейшее улучшение было получено Волганом Праттом. Если все смещения при сортировке выбираются из множества чисел вида <tex>2^p3^q</tex>, меньших <tex>N</tex>, то время выполнения алгоритма будет порядка <tex>Nlog^2{N}</tex>.
+Дальнейшее улучшение было получено Волганом Праттом. Если все смещения при сортировке выбираются из множества чисел вида <tex>2^p3^q</tex>, меньших <tex>N</tex>, то время выполнения алгоритма будет порядка <tex>О(Nlog^2{N})</tex>.
 == Смотри также ==

@@ Строка 2: / Строка 2: @@
 ==Алгоритм==
-Каждый проход в алгоритме характеризуется смещением <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>t = \left \lfloor log_2 {N} \right \rfloor - 1</tex>. Возможны и другие смещения, но <tex>h_0 = 1</tex> всегда.
+Шелл предлагал использовать <tex>h_t = N/2</tex>, <tex>h_{t-1} = h_t/2</tex>, ..., <tex>h_0 = 1</tex>, здесь <tex>t</tex> количество проходов минус один. Возможны и другие смещения, но <tex>h_0 = 1</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.''' Отсортируем элементы каждого списка [[Сортировка вставками|сортировкой вставками]].
 * '''Шаг 3.''' Объединим списки обратно в массив. Уменьшим <tex>i</tex>, если <tex>i</tex> неотрицательно вернемся к шагу 1.
@@ Строка 13: / Строка 13: @@
 ==Пример==
-Возьмем массив <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:#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> ''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''
@@ Строка 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> ''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''
@@ Строка 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> ''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''
@@ Строка 75: / Строка 75: @@
 ==Анализ метода Шелла==
 Понятно, что сложность алгоритма зависит от оптимальности выбора набора <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> упорядоченным.
 {{Теорема
@@ Строка 85: / Строка 86: @@
 <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
@@ Строка 94: / Строка 97: @@
 <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>N^{1.5}</tex> преодолеть невозможно, но если убрать ограничение <tex> h_{s+1}\,\bmod\,h_s = 0</tex> его можно преодолеть.
 {{Теорема
@@ Строка 112: / Строка 118: @@
 Важно, что эта теорема дает оценку времени выполнения алгоритма в худшем случае.
-Дальнейшее улучшение было получено Волганом Праттом. Если все смещения при сортировке выбираются из множества чисел вида <tex>2^p3^q</tex>, меньших <tex>N</tex>, то время выполнения алгоритма будет порядка <tex>N(logN)^2</tex>.
+Дальнейшее улучшение было получено Волганом Праттом. Если все смещения при сортировке выбираются из множества чисел вида <tex>2^p3^q</tex>, меньших <tex>N</tex>, то время выполнения алгоритма будет порядка <tex>Nlog^2{N}</tex>.
 == Смотри также ==
 * [[Сортировка выбором]]
 * [[Быстрая сортировка]]
@@ Строка 126: / Строка 133: @@
 [[Категория: Дискретная математика и алгоритмы]]
-[[Категория: Сортировка ]]
+[[Категория: Сортировка]]