/*Параллельная сортировка Шелла*/
#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;
}