shell sort parallel winapi LAB3 pp

shell sort parallel winapi

// ShellWinApi.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <iostream>

using namespace std;

const int N = 100000;
const int thread_count = 4;

int *arr = new int[N];
int *arr2 = new int[N];

void fillArray(int * arr, int N)
{
	for (int i = 0; i < N; i++)
	{
		arr[i] = rand();
	}
}
void printArr(int *arr)
{
	for (int i = 0; i < 50; i++)
		printf("%d ", arr[i]);
}

int *merge(int *a, int n, int *b, int m){

	int *c = new int[n + m];
	int i = 0, j = 0, k = 0;
	while (i <= n && j <= m){

		if (a[i] < b[j]){

			c[k] = a[i];
			i++;
		}
		else {

			c[k] = b[j];
			j++;
		}
		k++;
	}
	while (i < n){

		c[k] = a[i];
		i++;
		k++;
	}
	while (j < m){

		c[k] = b[j];
		j++;
		k++;
	}
	return c;
}


/* Пример из книги Герберта Шилдта */
void shell(int *items, int count)
{
	register int i, j, gap, k;
	int x, a[5];

	a[0] = 9; a[1] = 5; a[2] = 3; a[3] = 2; a[4] = 1;

	for (k = 0; k < 5; k++) {
		gap = a[k];
		for (i = gap; i < count; ++i) {
			x = items[i];
			for (j = i - gap; (x < items[j]) && (j >= 0); j = j - gap)
				items[j + gap] = items[j];
			items[j + gap] = x;
		}
	}
}

struct data
{
	int N;
	int *arr;
};

DWORD WINAPI shell_thread(data* params)
{
	int *items = params->arr;
	int count = params->N;
	//shell(A, N);

	register int i, j, gap, k;
	int x, a[5];

	a[0] = 9; a[1] = 5; a[2] = 3; a[3] = 2; a[4] = 1;

	for (k = 0; k < 5; k++) {
		gap = a[k];
		for (i = gap; i < count; ++i) {
			x = items[i];
			for (j = i - gap; (x < items[j]) && (j >= 0); j = j - gap)
				items[j + gap] = items[j];
			items[j + gap] = x;
		}
	}
	return 0u;
}

void ShellsSortParallel(int *array, int size)
{
	HANDLE thr[thread_count];
	for (int i = 0; i < thread_count; i++)
	{
		data *d1 = new data();
		d1->N = size / thread_count;
		d1->arr = array+(size / thread_count)*i;
		thr[i] = CreateThread(0, 0, (LPTHREAD_START_ROUTINE)shell_thread, d1, 0, NULL);
	}
	WaitForMultipleObjects(thread_count, thr, TRUE, INFINITE);
	int *res = new int[size / thread_count];
	for (int i = 0; i < thread_count; i++)
	{
		if (i == 0)
			memcpy(res, array, sizeof(int)* N / thread_count);
		else
			res = merge(res, (N / thread_count)*(i), &(array[N / thread_count*i]), N / thread_count);
	}
	memcpy(array, res, sizeof (int)*N);
}


int _tmain(int argc, _TCHAR* argv[])
{
	cout << 3 / 2 << endl;
	fillArray(arr, N);
	printf("Random array:\n");
	printArr(arr);
	memcpy(arr2, arr, sizeof(int)*N);
	//fillArray(arr2, N);
	printf("\nRandom array2:\n");
	printArr(arr2);
	int iStartTime = GetTickCount();
	shell(arr, N);
	int iEndTime = GetTickCount();
	int iDiff = iEndTime - iStartTime;
	cout << endl << "Sort time " << iDiff << "ms" << endl;
	printf("Sorted array:\n");
	printArr(arr);

	iStartTime = GetTickCount();
	ShellsSortParallel(arr2, N);
	iEndTime = GetTickCount();
	iDiff = iEndTime - iStartTime;
	cout << endl << "Parallel sort time " << iDiff << "ms" << endl;

	printf("Sorted array2:\n");
	printArr(arr2);

	getchar();
	return 0;
}