Участник:ElaginMD - История изменений

ElaginMD: /* Литература */

2025-10-27T21:13:00Z

Литература

← Предыдущая версия		Версия от 21:13, 27 октября 2025
Строка 1:		Строка 1:
	~~== Литература ==~~

ElaginMD: /* Свойства и структура алгоритмов */

2025-10-27T21:12:42Z

Свойства и структура алгоритмов

← Предыдущая версия		Версия от 21:12, 27 октября 2025
Строка 1:		Строка 1:
	~~== Свойства и структура алгоритмов ==~~
	~~=== Общее описание алгоритма ===~~
	'''Сортировка Шелла''', более известная как «сортировка с убывающим шагом». Алгоритм выполняет несколько проходов по списку, и каждый раз сортирует несколько наборов одинакового размера, используя сортировку вставкой. Размер сортируемого набора увеличивается с каждым проходом по списку, пока он не будет состоять из всего списка. Это позволяет сортировке вставкой выполнять каждую итерацию практически в лучшем случае со сложностью, приближающейся к <math>O(n)</math>.
	Элементы, содержащиеся в каждом наборе, не являются смежными, а именно, если есть <math>i</math> наборов, то набор состоит из каждого <math>i</math>-го элемента.<ref name="VVVVVV">Скворцова, Л. А. Структуры и алгоритмы обработки данных : учебно-методическое пособие / Л. А. Скворцова, К. В. Гусев, С. М. Трушин. — Москва : РТУ МИРЭА, 2021. — 235 с. </ref>
	~~<br><br>~~

	Например, если есть 3 набора, то первый набор будет содержать элементы, расположенные на позициях 1, 4, 7 и так далее. Второй набор будет содержать элементы, расположенные на позициях 2, 5, 8 и так далее; а третий набор будет содержать элементы, расположенные на позициях 3, 6, 9 и так далее.

	~~=== Математическое описание алгоритма ===~~

	~~Пусть, дан массив <math>A = [a_i, a_{i+1}, a_{i+2}, …a_n]</math>, где <math>i</math> – индекс массива;~~
	~~<math>n</math> – количество элементов в массиве {<math>{1,..,n}</math>}.~~
	~~<br>~~
	На первом шаге алгоритма происходит упорядочивание элементов <math>n/2</math> пар, <math>(a_i , a_{n/2+i})</math> для <math>1 ≤ i ≤ n/2</math>. Далее на втором шаге упорядочиваются элементы в <math>n/4</math> группах из четырех элементов <math>(a_i , a_{n / 4+ 1} , a_{n / 2+ 1} , a_{3 n / 4+ 1} )</math> для <math>1 ≤ i ≤ n/4</math>. На третьем шаге упорядочиваются элементы уже в <math>n/4</math> группах из восьми элементов и т.д. На последнем шаге упорядочиваются элементы сразу во всем массиве <math>(a_1 , a_2 ,…, a_n )</math>. На каждом шаге для упорядочивания полученных наборов элементов, используется метод сортировки вставками. Как можно заметить, общее количество итераций алгоритма Шелла является равным <math>log_2(n)</math><ref name="VVVVV1">Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Вильямс, 2001 — 384 с. </ref>.

	~~=== Вычислительное ядро алгоритма ===~~
	Вычислительным ядром алгоритма сортировки Шелла является сортировка вставками. На каждом шаге алгоритм разбивает исходный массив на несколько подмассивов с определенным интервалом, и каждый из этих подмассивов сортируется методом вставок.

	~~=== Макроструктура алгоритма ===~~
	В реализации данного алгоритма в качестве основного вычислительного ядра используется алгоритм сортировки вставками.
	~~<br>~~
	~~==== Сортировка вставками ====~~
	'''Сортировка вставками''', также известен как insertion sort - алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.<ref name="VV1VVV">Кнут Д. Э. 5.2 Внутренняя сортировка // Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. </ref>
	~~<br><br>~~
	'''Принцип работы алгоритма''' заключается в том, что на каждой итерации алгоритм берёт очередной элемент и сравнивает его со всеми элементами уже отсортированной части, находя подходящую позицию для вставки. Когда такая позиция находится, элементы, большие вставляемого, сдвигаются на одну позицию вправо, освобождая место для вставки текущего элемента. Этот процесс повторяется для всех элементов массива, начиная со второго и до последнего. Вычислительная сложность - <math>O({n^2})</math>.

	~~==== Псевдокод ====~~
	На вход алгоритму подаётся массив <math>A[1..n]</math>, состоящий из элементов <math>A[1]</math>,<math>A[2]</math>,...,<math>A[n]</math>, которые требуется отсортировать. Где <math>n</math> соответствует <big>''length''</big>(<math>A</math>) - размеру исходного массива. В результате работы во входном массиве оказывается отсортированная последовательность элементов.
	~~<br>~~
	~~step = length(A) / 2~~
	~~while step > 0:~~
	~~for i = step to length(A) - 1:~~
	~~j = i~~
	~~delta = j - step~~
	~~while delta >= 0 and A[delta] > A[j]: //insert sort.~~
	~~swap(A[delta], A[j])~~
	~~j = delta~~
	~~delta = j - step~~
	~~step = step / 2~~

	~~=== Ресурс параллелизма алгоритма ===~~
	~~=== Входные и выходные данные алгоритма ===~~
	На вход алгоритму подается одномерный массив произвольных сравниваемых элементов. Массив может быть произвольной длины и содержать элементы любого типа данных, для которых определена операция сравнения. Элементы массива могут быть как уникальными, так и содержать повторяющиеся элементы.
	~~<br>~~
	На выходе алгоритм возвращает одномерный массив той же длины, что и входной, содержащий те же элементы, но упорядоченные по возрастанию или убыванию в зависимости от реализации операции сравнения.

	== Литература ==		== Литература ==

ElaginMD: /* Псевдокод */

2025-10-26T09:22:34Z

Псевдокод

← Предыдущая версия		Версия от 09:22, 26 октября 2025
Строка 28:		Строка 28:
	На вход алгоритму подаётся массив <math>A[1..n]</math>, состоящий из элементов <math>A[1]</math>,<math>A[2]</math>,...,<math>A[n]</math>, которые требуется отсортировать. Где <math>n</math> соответствует <big>''length''</big>(<math>A</math>) - размеру исходного массива. В результате работы во входном массиве оказывается отсортированная последовательность элементов.		На вход алгоритму подаётся массив <math>A[1..n]</math>, состоящий из элементов <math>A[1]</math>,<math>A[2]</math>,...,<math>A[n]</math>, которые требуется отсортировать. Где <math>n</math> соответствует <big>''length''</big>(<math>A</math>) - размеру исходного массива. В результате работы во входном массиве оказывается отсортированная последовательность элементов.
	<br>		<br>
			step = length(A) / 2
	while step > 0:		while step > 0:
	for i = step ~~= length(A) / 2~~ to length(A) - 1:		for i = step to length(A) - 1:
	j = i		j = i
	delta = j - step		delta = j - step

ElaginMD: /* Общее описание алгоритма */

2025-10-25T20:54:00Z

Общее описание алгоритма

← Предыдущая версия		Версия от 20:54, 25 октября 2025
Строка 1:		Строка 1:
	== Свойства и структура алгоритмов ==		== Свойства и структура алгоритмов ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	'''Сортировка Шелла'''<ref name="VVVVVV">Скворцова, Л. А. Структуры и алгоритмы обработки данных : учебно-методическое пособие / Л. А. Скворцова, К. В. Гусев, С. М. Трушин. — Москва : РТУ МИРЭА, 2021. — 235 с. </ref>, более известная как «сортировка с убывающим шагом». Алгоритм выполняет несколько проходов по списку, и каждый раз сортирует несколько наборов одинакового размера, используя сортировку вставкой. Размер сортируемого набора увеличивается с каждым проходом по списку, пока он не будет состоять из всего списка. Это позволяет сортировке вставкой выполнять каждую итерацию практически в лучшем случае со сложностью, приближающейся к <math>O(n)</math>.		'''Сортировка Шелла''', более известная как «сортировка с убывающим шагом». Алгоритм выполняет несколько проходов по списку, и каждый раз сортирует несколько наборов одинакового размера, используя сортировку вставкой. Размер сортируемого набора увеличивается с каждым проходом по списку, пока он не будет состоять из всего списка. Это позволяет сортировке вставкой выполнять каждую итерацию практически в лучшем случае со сложностью, приближающейся к <math>O(n)</math>.
	Элементы, содержащиеся в каждом наборе, не являются смежными, а именно, если есть <math>i</math> наборов, то набор состоит из каждого <math>i</math>-го элемента.		Элементы, содержащиеся в каждом наборе, не являются смежными, а именно, если есть <math>i</math> наборов, то набор состоит из каждого <math>i</math>-го элемента.<ref name="VVVVVV">Скворцова, Л. А. Структуры и алгоритмы обработки данных : учебно-методическое пособие / Л. А. Скворцова, К. В. Гусев, С. М. Трушин. — Москва : РТУ МИРЭА, 2021. — 235 с. </ref>
	<br><br>		<br><br>

	Например, если есть 3 набора, то первый набор будет содержать элементы, расположенные на позициях 1, 4, 7 и так далее. Второй набор будет содержать элементы, расположенные на позициях 2, 5, 8 и так далее; а третий набор будет содержать элементы, расположенные на позициях 3, 6, 9 и так далее.		Например, если есть 3 набора, то первый набор будет содержать элементы, расположенные на позициях 1, 4, 7 и так далее. Второй набор будет содержать элементы, расположенные на позициях 2, 5, 8 и так далее; а третий набор будет содержать элементы, расположенные на позициях 3, 6, 9 и так далее.

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===

ElaginMD: /* Математическое описание алгоритма */

2025-10-25T20:52:58Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 20:52, 25 октября 2025
Строка 11:		Строка 11:
	<math>n</math> – количество элементов в массиве {<math>{1,..,n}</math>}.		<math>n</math> – количество элементов в массиве {<math>{1,..,n}</math>}.
	<br>		<br>
	На первом шаге алгоритма~~<ref name="VVVVV1">Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Вильямс, 2001 — 384 с. </ref>~~ происходит упорядочивание элементов <math>n/2</math> пар, <math>(a_i , a_{n/2+i})</math> для <math>1 ≤ i ≤ n/2</math>. Далее на втором шаге упорядочиваются элементы в <math>n/4</math> группах из четырех элементов <math>(a_i , a_{n / 4+ 1} , a_{n / 2+ 1} , a_{3 n / 4+ 1} )</math> для <math>1 ≤ i ≤ n/4</math>. На третьем шаге упорядочиваются элементы уже в <math>n/4</math> группах из восьми элементов и т.д. На последнем шаге упорядочиваются элементы сразу во всем массиве <math>(a_1 , a_2 ,…, a_n )</math>. На каждом шаге для упорядочивания полученных наборов элементов, используется метод сортировки вставками. Как можно заметить, общее количество итераций алгоритма Шелла является равным <math>log_2(n)</math>.		На первом шаге алгоритма происходит упорядочивание элементов <math>n/2</math> пар, <math>(a_i , a_{n/2+i})</math> для <math>1 ≤ i ≤ n/2</math>. Далее на втором шаге упорядочиваются элементы в <math>n/4</math> группах из четырех элементов <math>(a_i , a_{n / 4+ 1} , a_{n / 2+ 1} , a_{3 n / 4+ 1} )</math> для <math>1 ≤ i ≤ n/4</math>. На третьем шаге упорядочиваются элементы уже в <math>n/4</math> группах из восьми элементов и т.д. На последнем шаге упорядочиваются элементы сразу во всем массиве <math>(a_1 , a_2 ,…, a_n )</math>. На каждом шаге для упорядочивания полученных наборов элементов, используется метод сортировки вставками. Как можно заметить, общее количество итераций алгоритма Шелла является равным <math>log_2(n)</math><ref name="VVVVV1">Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Вильямс, 2001 — 384 с. </ref>.

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===

ElaginMD: /* Сортировка вставками */

2025-10-25T20:50:52Z

Сортировка вставками

← Предыдущая версия		Версия от 20:50, 25 октября 2025
Строка 21:		Строка 21:
	==== Сортировка вставками ====		==== Сортировка вставками ====
	'''Сортировка вставками''', также известен как insertion sort - алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.<ref name="VV1VVV">Кнут Д. Э. 5.2 Внутренняя сортировка // Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. </ref>		'''Сортировка вставками''', также известен как insertion sort - алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.<ref name="VV1VVV">Кнут Д. Э. 5.2 Внутренняя сортировка // Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. </ref>
	<br>		<br><br>
	'''Принцип работы алгоритма''' заключается в том, что на каждой итерации алгоритм берёт очередной элемент и сравнивает его со всеми элементами уже отсортированной части, находя подходящую позицию для вставки. Когда такая позиция находится, элементы, большие вставляемого, сдвигаются на одну позицию вправо, освобождая место для вставки текущего элемента. Этот процесс повторяется для всех элементов массива, начиная со второго и до последнего.		'''Принцип работы алгоритма''' заключается в том, что на каждой итерации алгоритм берёт очередной элемент и сравнивает его со всеми элементами уже отсортированной части, находя подходящую позицию для вставки. Когда такая позиция находится, элементы, большие вставляемого, сдвигаются на одну позицию вправо, освобождая место для вставки текущего элемента. Этот процесс повторяется для всех элементов массива, начиная со второго и до последнего. Вычислительная сложность - <math>O({n^2})</math>.

	==== Псевдокод ====		==== Псевдокод ====

ElaginMD: /* Сортировка вставками */

2025-10-25T20:46:14Z

Сортировка вставками

← Предыдущая версия		Версия от 20:46, 25 октября 2025
Строка 20:		Строка 20:
	<br>		<br>
	==== Сортировка вставками ====		==== Сортировка вставками ====
	'''Сортировка вставками'''~~<ref name="VVVVV1"></ref>~~, также известен как insertion sort - ~~это~~ алгоритм сортировки, ~~который последовательно помещает~~ каждый элемент ~~входного массива~~ в ~~его правильную позицию в уже отсортированной части массива~~.		'''Сортировка вставками''', также известен как insertion sort - алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.<ref name="VV1VVV">Кнут Д. Э. 5.2 Внутренняя сортировка // Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. </ref>
	<br>		<br>
	'''Принцип работы алгоритма''' заключается в том, что на каждой итерации алгоритм берёт очередной элемент и сравнивает его со всеми элементами уже отсортированной части, находя подходящую позицию для вставки. Когда такая позиция находится, элементы, большие вставляемого, сдвигаются на одну позицию вправо, освобождая место для вставки текущего элемента. Этот процесс повторяется для всех элементов массива, начиная со второго и до последнего.		'''Принцип работы алгоритма''' заключается в том, что на каждой итерации алгоритм берёт очередной элемент и сравнивает его со всеми элементами уже отсортированной части, находя подходящую позицию для вставки. Когда такая позиция находится, элементы, большие вставляемого, сдвигаются на одну позицию вправо, освобождая место для вставки текущего элемента. Этот процесс повторяется для всех элементов массива, начиная со второго и до последнего.

ElaginMD: /* Псевдокод */

2025-10-25T20:40:44Z

Псевдокод

← Предыдущая версия		Версия от 20:40, 25 октября 2025
Строка 31:		Строка 31:
	j = i		j = i
	delta = j - step		delta = j - step
	while delta >= 0 and A[delta] > A[j]: //(insert sort)		while delta >= 0 and A[delta] > A[j]: //insert sort.
	swap(A[delta], A[j])		swap(A[delta], A[j])
	j = delta		j = delta

ElaginMD: /* Псевдокод */

2025-10-25T20:38:08Z

Псевдокод

← Предыдущая версия		Версия от 20:38, 25 октября 2025
Строка 27:		Строка 27:
	На вход алгоритму подаётся массив <math>A[1..n]</math>, состоящий из элементов <math>A[1]</math>,<math>A[2]</math>,...,<math>A[n]</math>, которые требуется отсортировать. Где <math>n</math> соответствует <big>''length''</big>(<math>A</math>) - размеру исходного массива. В результате работы во входном массиве оказывается отсортированная последовательность элементов.		На вход алгоритму подаётся массив <math>A[1..n]</math>, состоящий из элементов <math>A[1]</math>,<math>A[2]</math>,...,<math>A[n]</math>, которые требуется отсортировать. Где <math>n</math> соответствует <big>''length''</big>(<math>A</math>) - размеру исходного массива. В результате работы во входном массиве оказывается отсортированная последовательность элементов.
	<br>		<br>
	~~<code>~~
	while step > 0:		while step > 0:
	for i = step = length(A) / 2 to length(A) - 1:		for i = step = length(A) / 2 to length(A) - 1:
	j = i		j = i
	delta = j - step		delta = j - step
	while delta >= 0 and A[delta] > A[j]: //(insert sort)		while delta >= 0 and A[delta] > A[j]: //(insert sort)
	swap(A[delta], A[j])		swap(A[delta], A[j])
	j = delta		j = delta
	delta = j - step		delta = j - step
	step = step / 2		step = step / 2
	~~</code>~~

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

ElaginMD: /* Псевдокод */

2025-10-25T20:33:32Z

Псевдокод

← Предыдущая версия		Версия от 20:33, 25 октября 2025
Строка 28:		Строка 28:
	<br>		<br>
	<code>		<code>
	while step > 0:		while step > 0:
	for i = step = length(A) / 2 to length(A) - 1:		for i = step = length(A) / 2 to length(A) - 1:
	j = i		j = i
	delta = j - step		delta = j - step
	while delta >= 0 and A[delta] > A[j]: //(insert sort)		while delta >= 0 and A[delta] > A[j]: //(insert sort)
	swap(A[delta], A[j])		swap(A[delta], A[j])
	j = delta		j = delta
	delta = j - step		delta = j - step
	step = step / 2		step = step / 2
	</code>		</code>