LINUX.ORG.RU

Распараллелить сортировку Шелла open mp

 


0

1

Добрый день!! У меня задание, нужно распараллелить сортировку, но у меня прога работает как-то коряво, можете сказать что не так в проге

/*Параллельная сортировка Шелла*/
#include "stdafx.h" 
#include <iostream> 
#include <omp.h> 
#include <ctime>
#include <windows.h> 
using namespace std;
int main()
{
	setlocale(LC_ALL, "rus");
	int m;
	const int n = 199;
	int a[n];
	srand(time(NULL));
	cout << "\nИсходный массив: ";
	for (int i = 0; i < n; i++)
	{
		a[i] = rand()%n;
		//a[i] = n-i;
	}
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << "\n";
	cout << endl;
	cout << "Этапы сортировки массива: \n";
	cout << "\n";
	//алгоритм сортировки Шелла
    int step = n / 2;//инициализируем шаг. 
    while (step > 0)//пока шаг не 0 
	{
	#pragma omp parallel for num_threads(2)  
	for (int i = 0; i < (n - step); i++)
	{
		int j = i;
		//будем идти начиная с i-го элемента 
		while (j >= 0 && a[j] > a[j + step]) 
		{
			Sleep(1);
			#pragma omp critical
			//пока не пришли к началу массива 
			//и пока рассматриваемый элемент больше 
			//чем элемент находящийся на расстоянии шага 
		{ 
					//меняем их местами 
					int temp = a[j];
					a[j] = a[j + step];
					a[j + step] = temp;
					m = omp_get_thread_num(); 
					cout << "Поток " << m << " меняет местами элементы с номерами " << j << " и " << j + step << "\n";
					j--;
				}
		}
  }
			step = step / 2;//уменьшаем шаг 
 }
	cout << "\nОтсортированный массив: ";
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << "\n";
	system("pause");
	return 0;
} 

Ответ на: комментарий от Makhno

Например: есть массив из 10 элементов 0 3 33 23 54 10 45 22 12 1 он выдает 0 1 3 10 22 12 23 33 45 54 и потоки друг на друга ругаются

nike3456
() автор топика
Ответ на: комментарий от nike3456

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

Silerus ★★★★
()
Ответ на: комментарий от nike3456

нельзя

False. Можно разбивать на маленькие подмассивы и сортировать их простым последовательным insertion sort.

И вообще, я не сильно близко видел OpenMP, но там разве в распараллеленом цикле не должны быть i, j как-то защищены от гонки?

Makhno
()
Ответ на: комментарий от Makhno

Соврал:

any variable declared in a block following an OpenMP directive will be local to the executing thread

Makhno
()
Ответ на: комментарий от nike3456

Скажешь, куда с зачеткой бежать? Честно говоря, лучше переписать это - как-то не так оно параллелится. Выше уже давали подсказки.

Makhno
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.