#include <stdio.h>
#include <malloc.h>
#include <conio.h>
#include <Windows.h>
#include <iostream>
 
//сортировка методом Шелла
void ShellSort(int n, int mass[])
{
    int i, j, step;
    int tmp;
    for (step = n / 2; step > 0; step /= 2)
        for (i = step; i < n; i++)
        {
            tmp = mass[i];
            for (j = i; j >= step; j -= step)
            {
                if (tmp < mass[j - step])
                    mass[j] = mass[j - step];
                else
                    break;
            }
            mass[j] = tmp;
        }
}
 
int main()
{
    //ввод N
    int N;
    printf("Input N: ");
    scanf_s("%d", &N);
    //выделение памяти под массив
    int* mass;
    mass = (int *)malloc(N * sizeof(int));
    //ввод элементов массива
    printf("Input the array elements:\n");
    for (int i = 0; i < N; i++)
        scanf_s("%d", &mass[i]);
    //сортировка методом Шелла
    ShellSort(N, mass);
    //вывод отсортированного массива на экран
    printf("Sorted array:\n");
    for (int i = 0; i < N; i++)
        printf("%d ", mass[i]);
    printf("\n");
    //освобождение памяти
    free(mass);
    _getch();
    return 0;
}

/*Параллельная сортировка Шелла*/
#include "stdafx.h" 
#include <iostream> 
#include <Windows.h> 
#include <conio.h> 
#include <omp.h> 
#include <time.h> 
#include <ctime>
using namespace std;
int main()
{
	setlocale(LC_ALL, "rus");
	int m, y = 0;
	const int n = 5;
	int a[n];
	srand(time(NULL));
	cout << "\nИсходный массив: ";
	for (int i = 0; i < n; i++)
	{
		a[i] = rand()%n;
	}
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << "\n";
	cout << endl;
	cout << "Этапы сортировки массива: \n";
	cout << "\n";
	//алгоритм сортировки Шелла
#pragma omp parallel firstprivate(n)
	{
		m = omp_get_thread_num();
		int 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;
					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;
}

/*Параллельная сортировка Шелла*/
#include "stdafx.h" 
#include <iostream> 
#include <Windows.h> 
#include <conio.h> 
#include <omp.h> 
#include <time.h> 
#include <ctime>
using namespace std;
int main()
{
	setlocale(LC_ALL, "rus");
	double start_time, end_time;
	int m, y = 0;
	const int n = 120;
	int a[n];
	srand(time(NULL));
	cout << "\nИсходный массив: ";
	for (int i = 0; i < n; i++)
	{
		a[i] = rand()%n;
	}
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << "\n";
	cout << endl;
	cout << "Этапы сортировки массива: \n";
	cout << "\n";
	//алгоритм сортировки Шелла
	start_time = omp_get_wtime();
#pragma omp parallel firstprivate(n)
	{
		m = omp_get_thread_num();
		int step = n / 2;//инициализируем шаг. 
		while (step > 0)//пока шаг не 0 
		{
			#pragma omp parallel for
			for (int i = 0; i < (n - step); i++)
				#pragma omp critical 
			{
				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;
					cout << "Поток " << m << " меняет местами элементы с номерами " << j << " и " << j + step << "\n";
					j--;
				}
			}
			step = step / 2;//уменьшаем шаг 
		}
	}
	end_time = omp_get_wtime();
	cout << "\nОтсортированный массив: ";
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << "\n";
	cout << "Время на замер времени: " << end_time - start_time << endl;
	system("pause");
	return 0;
}