Участник:Alexeyshekhanov/Сортировка пузырьком - История изменений

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

2023-12-05T18:33:28Z

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

← Предыдущая версия		Версия от 18:33, 5 декабря 2023
Строка 5:		Строка 5:

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
	Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем n на 1 и повторяем шаги 1 и 2 для оставшихся элементов. Продолжаем выполнять проходы до тех пор, пока список не станет отсортированным.		Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: 1. Начнем с индекса <math>i = 0</math>. 2. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. 3. Если <math>A[i] > A[i+1]</math>, меняем их местами. 4. После первого прохода самый большой элемент окажется в конце списка. 5. Уменьшаем n на 1 и повторяем шаги 1 и 2 для оставшихся элементов. Продолжаем выполнять проходы до тех пор, пока список не станет отсортированным.

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

Alexeyshekhanov: /* Информационный граф */

2023-12-05T18:32:28Z

Информационный граф

← Предыдущая версия		Версия от 18:32, 5 декабря 2023
Строка 32:		Строка 32:
	Информационный граф состоит из <math>n</math> итераций, где разбиение элементов на пары начинается с нулевого элемента на каждой четной начинается, а на каждой нечетной с первого. Каждую такую пару может обрабатывать отдельный поток, независимо от других.		Информационный граф состоит из <math>n</math> итераций, где разбиение элементов на пары начинается с нулевого элемента на каждой четной начинается, а на каждой нечетной с первого. Каждую такую пару может обрабатывать отдельный поток, независимо от других.
	[[Файл:Информационный граф1.png\|мини\|Рис 1. Информационный граф алгоритма сортировки пузырьком]]		[[Файл:Информационный граф1.png\|мини\|Рис 1. Информационный граф алгоритма сортировки пузырьком]]
	Это можно увидеть на примере, который изображен на рис. 2		Это можно увидеть на примере, который изображен на рис. 2. Красным обведены элементы, которые сравниваются и "обмениваются" на данной итерации.

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

Alexeyshekhanov: /* Масштабируемость алгоритма и его реализации */

2023-12-05T18:30:04Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 18:30, 5 декабря 2023
Строка 52:		Строка 52:
	===Возможные способы и особенности параллельной реализации алгоритма===		===Возможные способы и особенности параллельной реализации алгоритма===
	===Масштабируемость алгоритма и его реализации===		===Масштабируемость алгоритма и его реализации===
			Масштабируемость алгоритма сортировки пузырьком определяется размером входных данных и количеством доступных потоков.
			1. В случае с входными данными, чем больше их размер, тем лучше масштабируемость.
			2. В случае же с доступными потоками, то не всегда их число прямо пропорционально влияет на скорость выполнения сортировки. С какого то количества потоков, в зависимости от размера входных данных, сортировка начинает выполняться все медленнее и медленнее из за накладных расходов, таких как создание потоков, их синхронизация и т.п.
	<gallery>		<gallery>
	4kb.~~jpg~~\|Зависимость времени сортировки от количества потоков при размере входных данных 4 Кбайт.		4kb.png\|Зависимость времени сортировки от количества потоков при размере входных данных 4 Кбайт.
	40kb.~~jpg~~\|Зависимость времени сортировки от количества потоков при размере входных данных 40 Кбайт.		40kb.png\|Зависимость времени сортировки от количества потоков при размере входных данных 40 Кбайт.
	400kb.~~jpg~~\|Зависимость времени сортировки от количества потоков при размере входных данных 400 Кбайт.		400kb.png\|Зависимость времени сортировки от количества потоков при размере входных данных 400 Кбайт.
	4mb.~~jpg~~\|Зависимость времени сортировки от количества потоков при размере входных данных 4 Мбайт.		4mb.png\|Зависимость времени сортировки от количества потоков при размере входных данных 4 Мбайт.
	</gallery>		</gallery>

Alexeyshekhanov: /* Масштабируемость алгоритма и его реализации */

2023-12-05T18:26:43Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 18:26, 5 декабря 2023
Строка 52:		Строка 52:
	===Возможные способы и особенности параллельной реализации алгоритма===		===Возможные способы и особенности параллельной реализации алгоритма===
	===Масштабируемость алгоритма и его реализации===		===Масштабируемость алгоритма и его реализации===
			<gallery>
			4kb.jpg\|Зависимость времени сортировки от количества потоков при размере входных данных 4 Кбайт.
			40kb.jpg\|Зависимость времени сортировки от количества потоков при размере входных данных 40 Кбайт.
			400kb.jpg\|Зависимость времени сортировки от количества потоков при размере входных данных 400 Кбайт.
			4mb.jpg\|Зависимость времени сортировки от количества потоков при размере входных данных 4 Мбайт.
			</gallery>

	===Динамические характеристики и эффективность реализации алгоритма===		===Динамические характеристики и эффективность реализации алгоритма===
	===Выводы для классов архитектур===		===Выводы для классов архитектур===

Alexeyshekhanov: /* Информационный граф */

2023-12-05T18:16:49Z

Информационный граф

← Предыдущая версия		Версия от 18:16, 5 декабря 2023
Строка 30:		Строка 30:

	===Информационный граф===		===Информационный граф===
			Информационный граф состоит из <math>n</math> итераций, где разбиение элементов на пары начинается с нулевого элемента на каждой четной начинается, а на каждой нечетной с первого. Каждую такую пару может обрабатывать отдельный поток, независимо от других.
	[[Файл:Информационный граф1.png\|мини\|Рис 1. Информационный граф алгоритма сортировки пузырьком]]		[[Файл:Информационный граф1.png\|мини\|Рис 1. Информационный граф алгоритма сортировки пузырьком]]
			Это можно увидеть на примере, который изображен на рис. 2

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

Alexeyshekhanov: /* Ресурс параллелизма алгоритма */

2023-12-05T18:10:12Z

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

← Предыдущая версия		Версия от 18:10, 5 декабря 2023
Строка 34:		Строка 34:
	===Ресурс параллелизма алгоритма===		===Ресурс параллелизма алгоритма===
	Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.		Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

			[[Файл:Example.jpg\|мини\|Рис 2. Пример с массивом размера 6, количеством потоков 3]]

	В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность <math display="inline">\Theta(1)</math>, а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет <math display="inline">\Theta(n)</math>.		В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность <math display="inline">\Theta(1)</math>, а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет <math display="inline">\Theta(n)</math>.

	Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.		Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.
	~~[[Файл:Example.jpg\|мини\|Рис 2. Пример с массивом размера 6, количеством потоков 3]]~~

	===Входные и выходные данные алгоритма===		===Входные и выходные данные алгоритма===

Alexeyshekhanov: /* Ресурс параллелизма алгоритма */

2023-12-05T18:09:32Z

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

← Предыдущая версия		Версия от 18:09, 5 декабря 2023
Строка 38:		Строка 38:

	Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.		Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.
			[[Файл:Example.jpg\|мини\|Рис 2. Пример с массивом размера 6, количеством потоков 3]]

	===Входные и выходные данные алгоритма===		===Входные и выходные данные алгоритма===

Alexeyshekhanov: /* Информационный граф */

2023-12-05T18:06:21Z

Информационный граф

← Предыдущая версия		Версия от 18:06, 5 декабря 2023
Строка 30:		Строка 30:

	===Информационный граф===		===Информационный граф===
	[[Файл:~~Infograph2~~.~~jpg~~\|мини\|Рис.1. Информационный граф алгоритма сортировки пузырьком]]		[[Файл:Информационный граф1.png\|мини\|Рис 1. Информационный граф алгоритма сортировки пузырьком]]

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

Alexeyshekhanov: /* Ресурс параллелизма алгоритма */

2023-12-05T17:58:16Z

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

← Предыдущая версия		Версия от 17:58, 5 декабря 2023
Строка 35:		Строка 35:
	Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.		Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

	В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность О(1), а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет О(n).		В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность <math display="inline">\Theta(1)</math>, а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет <math display="inline">\Theta(n)</math>.

	Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.		Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

Alexeyshekhanov: /* Ресурс параллелизма алгоритма */

2023-12-05T17:57:42Z

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

← Предыдущая версия		Версия от 17:57, 5 декабря 2023
Строка 38:		Строка 38:

	Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.		Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

	~~<gallery>~~
	~~[[Файл:ParBubble2.png\|мини\|подпись]]~~
	~~</gallery>~~

	===Входные и выходные данные алгоритма===		===Входные и выходные данные алгоритма===