Участник:Yaselivoxin/Алгоритм - История изменений

Yaselivoxin в 11:42, 18 ноября 2025

2025-11-18T11:42:25Z

Yaselivoxin в 11:50, 17 ноября 2025

2025-11-17T11:50:49Z

← Предыдущая версия		Версия от 11:50, 17 ноября 2025
Строка 1:		Строка 1:
	{{algorithm		{{algorithm
	\| name = Алгоритм быстрой сортировки Quicksort		\| name = Алгоритм быстрой сортировки Quicksort
	\| serial_complexity = <math>o(n^2)</math>		\| serial_complexity = <math>O(n^2)</math>
	\| pf_height = <math>o(log n)</math>		\| pf_height = <math>O(log n)</math>
	\| pf_width = <math>o(n)</math>		\| pf_width = <math>O(n)</math>
	\| input_data = <math>n</math>		\| input_data = <math>n</math>
	\| output_data = <math>n</math>		\| output_data = <math>n</math>

Yaselivoxin в 06:52, 13 ноября 2025

2025-11-13T06:52:46Z

← Предыдущая версия		Версия от 06:52, 13 ноября 2025
Строка 1:		Строка 1:
			{{algorithm
			\| name = Алгоритм быстрой сортировки Quicksort
			\| serial_complexity = <math>o(n^2)</math>
			\| pf_height = <math>o(log n)</math>
			\| pf_width = <math>o(n)</math>
			\| input_data = <math>n</math>
			\| output_data = <math>n</math>
			}}

			Основные авторы описания: [[Участник:Yaselivoxin\|Я.А.Селивохин]].

	Алгоритм быстрой сортировки QuickSort		Алгоритм быстрой сортировки QuickSort
	== Свойства и структура алгоритмов ==		== Свойства и структура алгоритмов ==

Yaselivoxin в 06:39, 13 ноября 2025

2025-11-13T06:39:52Z

← Предыдущая версия		Версия от 06:39, 13 ноября 2025
Строка 16:		Строка 16:
	''a<sub>1</sub>'' ≤ ''a<sub>2</sub>'' ≤ ... ≤ ''a<sub>n</sub>''.		''a<sub>1</sub>'' ≤ ''a<sub>2</sub>'' ≤ ... ≤ ''a<sub>n</sub>''.

	Код алгоритма на С++:		Код алгоритма на С:

	<source lang="с++">		<source lang="с">
	int partition(~~std::vector<~~int>& A, int lo, int hi) {
			int partition(int* A, int lo, int hi) {
	int pivot = A[hi]; // Опорный элемент		int pivot = A[hi]; // Опорный элемент
	int i = lo - 1; // Индекс для меньших элементов		int i = lo - 1; // Индекс для меньших элементов
Строка 25:		Строка 26:
	if (A[j] <= pivot) {		if (A[j] <= pivot) {
	++i;		++i;
	~~std::swap(~~A[i], A[j]); ~~// Меняем местами элементы~~		// Меняем местами элементы
			int temp = A[i];
			A[i] = A[j];
			A[j] = temp;
	}		}
	}		}
	~~std::swap(~~A[i + 1], A[hi]); ~~// Ставим опорный элемент на правильную позицию~~		// Ставим опорный элемент на правильную позицию
			int temp = A[i + 1];
			A[i + 1] = A[hi];
			A[hi] = temp;

	return i + 1; // Возвращаем индекс опорного элемента		return i + 1; // Возвращаем индекс опорного элемента
	}		}
Строка 53:		Строка 61:
	* Рекурсивная сортировка двух подмассивов.		* Рекурсивная сортировка двух подмассивов.

	Пример кода на C++:		Пример кода на C:

	<source lang="с++">		<source lang="с">
	~~// Рекурсивная функция быстрой сортировки~~		void quicksort(int* A, int lo, int hi) {
	void quicksort(~~std::vector<~~int>& A, int lo, int hi) {
	if (lo < hi) {		if (lo < hi) {
	int p = partition(A, lo, hi); // Разбиение массива		int p = partition(A, lo, hi); // Разбиение массива

Yaselivoxin в 06:37, 13 ноября 2025

2025-11-13T06:37:38Z

@@ Строка 117: / Строка 117: @@
      void quicksort(int *arr, int left, int right) {
-    int i = left, j = right;
+        int i = left, j = right;
-    int pivot = arr[(left + right) / 2];
+        int pivot = arr[(left + right) / 2];
-    int temp;
+        int temp;
-    while (i <= j) {
+        while (i <= j) {
-        while (arr[i] < pivot) i++;
+            while (arr[i] < pivot) i++;
-        while (arr[j] > pivot) j--;
+            while (arr[j] > pivot) j--;
-        if (i <= j) {
+             if (i <= j) {
-            temp = arr[i];
+                 temp = arr[i];
-            arr[i] = arr[j];
+                 arr[i] = arr[j];
-            arr[j] = temp;
+                 arr[j] = temp;
-            i++; j--;
+                 i++;
+         }
+        if (left < j) quicksort(arr, left, j);  // Рекурсивно сортируем левую часть
-    if (left < j) quicksort(arr, left, j);  // Рекурсивно сортируем левую часть
+        if (i < right) quicksort(arr, i, right);  // Рекурсивно сортируем правую часть
+     }
@@ Строка 147: / Строка 148: @@
      #define THRESHOLD 10000  // Минимальный размер подмассива для параллелизации
      void quicksort(int *arr, int left, int right, int depth) {
-    int i = left, j = right;
+        int i = left, j = right;
-    int pivot = arr[(left + right) / 2];
+        int pivot = arr[(left + right) / 2];
-    int temp;
+        int temp;
-    while (i <= j) {
+        while (i <= j) {
-        while (arr[i] < pivot) i++;
+            while (arr[i] < pivot) i++;
-        while (arr[j] > pivot) j--;
+            while (arr[j] > pivot) j--;
-        if (i <= j) {
+            if (i <= j) {
-            temp = arr[i];
+                temp = arr[i];
-            arr[i] = arr[j];
+                arr[i] = arr[j];
-            arr[j] = temp;
+                arr[j] = temp;
-             i++; j--;
+                i++;
+         }
 === Описание параллельных аспектов реализации ===

Yaselivoxin в 06:30, 13 ноября 2025

2025-11-13T06:30:25Z

← Предыдущая версия		Версия от 06:30, 13 ноября 2025
Строка 105:		Строка 105:

	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==

			===Особенности реализации последовательного алгоритма===
			Алгоритм QuickSort может быть реализован как в последовательной, так и в параллельной версиях. В основе алгоритма лежит стратегия, где массив делится на два подмассива относительно опорного элемента (pivot), и затем рекурсивно сортируются эти подмассивы.

			В простейшей последовательной версии алгоритма QuickSort, как правило, используется следующая логика:
			# Выбирается опорный элемент (например, средний элемент массива).
			# Массив разделяется на два подмассива: элементы, меньшие опорного, и элементы, большие опорного.
			# Рекурсивно сортируются эти два подмассива, пока каждый из них не станет отсортированным.

			Пример последовательной реализации (без параллельности):

			void quicksort(int *arr, int left, int right) {
			int i = left, j = right;
			int pivot = arr[(left + right) / 2];
			int temp;
			while (i <= j) {
			while (arr[i] < pivot) i++;
			while (arr[j] > pivot) j--;
			if (i <= j) {
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++; j--;
			}
			}
			if (left < j) quicksort(arr, left, j); // Рекурсивно сортируем левую часть
			if (i < right) quicksort(arr, i, right); // Рекурсивно сортируем правую часть
			}



			=== Параллельная реализация алгоритма ===
			Для увеличения производительности на многозадачных системах, таких как суперкомпьютеры, можно параллелить рекурсивные вызовы алгоритма QuickSort. Параллельная версия алгоритма QuickSort будет разделять массивы и обрабатывать их в несколько потоков на высоких уровнях рекурсии, используя директивы OpenMP.

			В приведенном ниже коде используется условие, что параллельные задачи создаются только для рекурсивных вызовов, где размер подмассива больше заданного порога THRESHOLD. Это позволяет избежать излишних накладных расходов на параллельную обработку маленьких подмассивов.


			#include <stdio.h>
			#include <stdlib.h>
			#include <omp.h>
			#define THRESHOLD 10000 // Минимальный размер подмассива для параллелизации
			void quicksort(int *arr, int left, int right, int depth) {
			int i = left, j = right;
			int pivot = arr[(left + right) / 2];
			int temp;
			while (i <= j) {
			while (arr[i] < pivot) i++;
			while (arr[j] > pivot) j--;
			if (i <= j) {
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++; j--;
			}
			}
			// Последовательная сортировка мелких подмассивов
			if (right - left < THRESHOLD) {
			if (left < j) quicksort(arr, left, j, depth + 1);
			if (i < right) quicksort(arr, i, right, depth + 1);
			}
			else {
			// Параллельные ветви создаются только на верхних уровнях
			#pragma omp task shared(arr) if (depth < 4)
			quicksort(arr, left, j, depth + 1);
			#pragma omp task shared(arr) if (depth < 4)
			quicksort(arr, i, right, depth + 1);
			}
			}
			int main() {
			int n = 1000000000; // Размер массива
			int arr = malloc(n sizeof(int));
			if (!arr) {
			printf("Memory allocation failed!\n");
			return 1;
			}
			// Заполнение массива случайными числами
			for (int i = 0; i < n; i++)
			arr[i] = rand();
			double start = omp_get_wtime(); // Начало замера времени
			// Запуск параллельного выполнения с использованием OpenMP
			#pragma omp parallel
			{
			#pragma omp single
			quicksort(arr, 0, n - 1, 0);
			}
			double end = omp_get_wtime(); // Конец замера времени
			printf("Elapsed time: %.4f seconds\n", end - start); // Вывод времени выполнения
			free(arr); // Освобождение памяти
			return 0;
			}


			=== Описание параллельных аспектов реализации ===

			В данном коде используются директивы OpenMP:

			* #pragma omp parallel: инициирует параллельное выполнение с использованием нескольких потоков.
			* #pragma omp task: создаёт параллельные задачи для сортировки левой и правой части массива на каждом уровне рекурсии. Задачи создаются только для рекурсии на уровнях, где глубина рекурсии меньше 4 (это значение можно подбирать и настраивать).
			* #pragma omp single: гарантирует, что только один поток будет выполнять начальный вызов quicksort, в то время как остальные потоки выполнят задачи параллельно.

			=== Результаты и оценка производительности ===

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

Yaselivoxin в 18:15, 1 ноября 2025

2025-11-01T18:15:47Z

← Предыдущая версия		Версия от 18:15, 1 ноября 2025
Строка 16:		Строка 16:
	''a<sub>1</sub>'' ≤ ''a<sub>2</sub>'' ≤ ... ≤ ''a<sub>n</sub>''.		''a<sub>1</sub>'' ≤ ''a<sub>2</sub>'' ≤ ... ≤ ''a<sub>n</sub>''.

	~~Псевдокод~~ алгоритма:		Код алгоритма на С++:

	<source lang="с++">		<source lang="с++">

Yaselivoxin в 18:14, 1 ноября 2025

2025-11-01T18:14:53Z

← Предыдущая версия		Версия от 18:14, 1 ноября 2025
Строка 80:		Строка 80:

	[[Файл:structured_quick_sort_graph.png\|thumb\|center\|300px\|Рис.1. Информационная структура алгоритма быстрой сортировки]]		[[Файл:structured_quick_sort_graph.png\|thumb\|center\|300px\|Рис.1. Информационная структура алгоритма быстрой сортировки]]

			Вводимые замены:
			* ОЭ - опорный элемент
			* ЛЧ - левая часть
			* ПЧ - правая часть

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

Yaselivoxin: Обновлен 1.7

2025-11-01T18:13:57Z

Обновлен 1.7

← Предыдущая версия		Версия от 18:13, 1 ноября 2025
Строка 79:		Строка 79:
	Алгоритм быстрой сортировки имеет иерархическую структуру, где каждый уровень рекурсии разделяет массив пополам. Это дерево рекурсии можно представить в виде графа, где вершины соответствуют рекурсивным вызовам и разбиению массива на подмассивы.		Алгоритм быстрой сортировки имеет иерархическую структуру, где каждый уровень рекурсии разделяет массив пополам. Это дерево рекурсии можно представить в виде графа, где вершины соответствуют рекурсивным вызовам и разбиению массива на подмассивы.

	[[Файл:structured_quick_sort_graph.png\|~~мини~~\|Информационная структура алгоритма быстрой сортировки]]		[[Файл:structured_quick_sort_graph.png\|thumb\|center\|300px\|Рис.1. Информационная структура алгоритма быстрой сортировки]]

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

Yaselivoxin в 18:06, 1 ноября 2025

2025-11-01T18:06:57Z

← Предыдущая версия		Версия от 18:06, 1 ноября 2025
Строка 78:		Строка 78:

	Алгоритм быстрой сортировки имеет иерархическую структуру, где каждый уровень рекурсии разделяет массив пополам. Это дерево рекурсии можно представить в виде графа, где вершины соответствуют рекурсивным вызовам и разбиению массива на подмассивы.		Алгоритм быстрой сортировки имеет иерархическую структуру, где каждый уровень рекурсии разделяет массив пополам. Это дерево рекурсии можно представить в виде графа, где вершины соответствуют рекурсивным вызовам и разбиению массива на подмассивы.

			[[Файл:structured_quick_sort_graph.png\|мини\|Информационная структура алгоритма быстрой сортировки]]

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

	Алгоритм быстрой сортировки обладает хорошим потенциалом для параллельной реализации. Основной параллелизм можно достичь за счет выполнения рекурсивных вызовов для левых и правых подмассивов параллельно. Для этого можно использовать многозадачность, например, с помощью библиотек OpenMP или стандартной библиотеки C++. Например, с использованием <source lang="с++">std::async</source~~><onlyinclude></onlyinclude~~>		Алгоритм быстрой сортировки обладает хорошим потенциалом для параллельной реализации. Основной параллелизм можно достичь за счет выполнения рекурсивных вызовов для левых и правых подмассивов параллельно. Для этого можно использовать многозадачность, например, с помощью библиотек OpenMP или стандартной библиотеки C++. Например, с использованием <source lang="с++">std::async</source>

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