mergeparallelsortwinapi

mergeparallelsortwinapi

// 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]);
}

//функция, сливающая массивы
void Merge(int *A, int first, int last)
{

	int middle, start, final, j;
	int *mas = new int[100500];
	middle = (first + last) / 2; //вычисление среднего элемента
	start = first; //начало левой части
	final = middle + 1; //начало правой части

	for (j = first; j <= last; j++) //выполнять от начала до конца
	if ((start <= middle) && ((final>last) || (A[start]<A[final])))
	{
		mas[j] = A[start];
		start++;
	}
	else
	{
		mas[j] = A[final];
		final++;
	}
	//возвращение результата в список
	for (j = first; j <= last; j++) A[j] = mas[j];
	delete[]mas;
}
//рекурсивная процедура сортировки
void MergeSort(int *A, int first, int last)
{

	if (first<last)
	{

		MergeSort(A, first, (first + last) / 2); //сортировка левой части

		MergeSort(A, (first + last) / 2 + 1, last); //сортировка правой части
		Merge(A, first, last); //слияние двух частей}


	}
}

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;
}


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

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

	MergeSort(items, 0, count);
	return 0u;
}

void MergeSortParallel(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)merge_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();
	MergeSort(arr,0, N);
	int iEndTime = GetTickCount();
	int iDiff = iEndTime - iStartTime;
	cout << endl << "Sort time " << iDiff << "ms" << endl;
	printf("Sorted array:\n");
	printArr(arr);

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

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

	getchar();
	return 0;
}