#include "stdafx.h"
#include <stdio.h>
#include <iostream> 
#include <Windows.h> 
#include <conio.h> 
#include <omp.h> 
using namespace std;
void ShellSort(int *a, int n) {
	//алгоритм сортировки Шелла 
	int m;
	int step;
#pragma omp parallel firstprivate(step) 

	{
		step = n / 2;//инициализируем шаг. 
		while (step > 0)//пока шаг не 0 
		{

#pragma omp for 
			for (int i = 0; i < (n - step); i++)
			{
				int j = i;
				//будем идти начиная с i-го элемента 
				while (j >= 0 && a[j] > a[j + step])
					//пока не пришли к началу массива 
					//и пока рассматриваемый элемент больше 
					//чем элемент находящийся на расстоянии шага 
				{
					//меняем их местами 
					int temp = a[j];
					a[j] = a[j + step];
					a[j + step] = temp;
					m = omp_get_thread_num();

					if (m == 0) {
						SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED | FOREGROUND_INTENSITY);
						cout << "Поток " << m << " меняет местами элементы с номерами " << j << " и " << j + step << "\n";
					}
					if (m == 1) {
						SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_GREEN | FOREGROUND_INTENSITY);

						cout << "Поток " << m << " меняет местами элементы с номерами " << j << " и " << j + step << "\n";
					}

					if (m == 2)
					{
						SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_BLUE | FOREGROUND_INTENSITY);

						cout << "Поток " << m << " меняет местами элементы с номерами " << j << " и " << j + step << "\n";
					}
					if (m == 3) {
						SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_INTENSITY);
						cout << "Поток " << m << " меняет местами элементы с номерами " << j << " и " << j + step << "\n";
					}
					j--;

				}
			}
			step = step / 2;//уменьшаем шаг 
		}}
}
int main(int argc, char* argv[])
{

	setlocale(LC_CTYPE, "rus");
	int n, m, b, y = 0;

	cout << "Количество элементов: ";
	cin >> n;
	int *a = new int[n];
	cout <<
		"1 - Ввод значений с клавиатуры \n"
		"2 - Рандомное заполнение \n";
	cin >> b;
	switch (b)

	{

	case 1:
	{
		for (int i = 0; i < n; i++)
		{
			cout << i + 1 << "-ый элемент: ";
			cin >> a[i];
		}} break;
	case 2:
	{
		int g;
		cout << "\nМаксимальное значение элемента: ";
		cin >> g;
		for (int i = 0; i < n; i++) { a[i] = rand() % g; }} break;
	}

	cout << "\nИсходный массив: ";
	for (int i = 0; i < n; ++i)
	{
		cout << a[i] << " ";
	}
	cout << "\n";
	cout << endl;

	cout << "Этапы сортировки массива: \n";
	cout << "\n";
	ShellSort(a, n);
	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
	cout << "\nОтсортированный массив: ";
	for (int i = 0; i < n; i++)
	{

		cout << a[i] << " ";
	}

	cout << "\n";
	system("pause");
	return 0;
}