bubble_sort.cpp

冒泡排序的串行算法和并行算法的比较

// bubble_sort.cpp : Defines the entry point for the console application.
//并行程序对于数组进行比较的时候是正确的。但是对于一个vector为什么答案就不是
//正确的呢?将vector转换成array后，发现结果也是对的。
//计算的时间，并行的时间是串行的30倍左右。要排列的数据量为386；
//不知道如果增大数据量，会不会有理想的结果。
//数据量达到1495时，并行只有串行的1倍多，继续增大数据量。
//数据量增大到23504时，并行还说串行的近2倍。
//用debug的时候运行的结果是错的，但是用release的时候结果是正确的。用向量和数组的结果是一致的。
//而且计算的时间也是合理的。


#include "stdafx.h"
#include<stdio.h>
#include "omp.h"
#include <vector>
#include <windows.h>
using namespace std;
//
//int aa[82] = { 12,25,2,56,561,36,98,88,5,58,45,485,75,24,87,
//67,11,122,12,111,5,534,643,2345,35,345,63,234,
//642,64,67,867,236,3466,345,535,36,654,37,74,57,
//12,25,2,56,561,36,98,88,5,58,45,485,75,24,87,
//67,11,122,12,111,5,534,643,2345,35,345,63,234,
//642,64,67,867,236,3466,345,535,36,654,37,74,57};


void serial_bubble_sort(vector<int>& a,int n )
{
	int k;
	int temp;
	for(int i = n-1; i > 0 ; i--)
		for(int j = 0; j < i; j++)
		{
			k = j + 1;
			if(a[j] > a [k] )
			{
				temp = a[j];
				a[j] = a[k];
				a[k] = temp;
			}
		}
}

void serial_bubble_sort(int a[],int n )
{
	int k;
	int temp;
	for(int i = n-1; i > 0 ; i--)
		for(int j = 0; j < i; j++)
		{
			k = j + 1;
			if(a[j] > a [k] )
			{
				temp = a[j];
				a[j] = a[k];
				a[k] = temp;
			}
		}
}

void parallel_bubble_sort(int a[], int n)
{
	int i;
	int k;
	int temp;
	for( i = 0; i < n-1; i++)
	{
		if(i%2 ==0 )
		{
#pragma omp parallel for 
			for(int j = 0; j < n-1; j += 2)
			{
				if(a[j] > a[j+1])
				{
					temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}
		else
		{
#pragma omp parallel for 
			for(int j = 1  ; j < n-1; j += 2)
			{
				if(a[j] > a[j+1])
				{
					temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}	
	}
}

void parallel_bubble_sort(vector<int>& a, int n)
{
	int i;
	int k;
	int temp;
	for( i = 0; i < n-1; i++)
	{
		if(i%2 ==0 )
		{
#pragma omp parallel for 
			for(int j = 0; j < n-1; j += 2)
			{
				if(a[j] > a[j+1])
				{
					temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}
		else
		{
#pragma omp parallel for 
			for(int j = 1  ; j < n-1; j += 2)
			{
				if(a[j] > a[j+1])
				{
					temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}	
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	FILE* pfile;
	vector<int> number;
	number.reserve(100000);
	int i = 0;
	int temp;
	if(!(pfile = fopen("data2.txt","r")))
		printf("Open Error!");
	while ( fscanf(pfile,"%d",&temp)!= EOF)
	{
		i++;
		number.push_back(temp);
		fscanf(pfile,"%*c");
	}
	int total;
	total = number.size();
	//int bb[47008];
	int* bb = &number[0];
	//bb = new int[total];
	int cc[47008];
	//for(int p = 0; p < total; p++)
	//{
	//	bb[p] = number[p];
	//	cc[p] = number[p];
	//}

	_int64 count_b;
	_int64 count_e;
	_int64 diff;

	/*parallel_bubble_sort(number,total);*/

	//QueryPerformanceCounter((LARGE_INTEGER*)&count_b);
	//serial_bubble_sort(cc,total);
	//QueryPerformanceCounter((LARGE_INTEGER*)&count_e);
	//diff = count_e - count_b;
	//printf("Serial time is   %I64d\n",diff);

	//QueryPerformanceCounter((LARGE_INTEGER*)& count_b);
	parallel_bubble_sort(bb,total);
	//QueryPerformanceCounter((LARGE_INTEGER*)& count_e);
	//diff = count_e - count_b;
	//printf("Parallel time is %I64d\n",diff);

	//for(int i = 0; i < 82; i++)
	//	printf("%d\n",aa[i]);
	//for(int j = 0; j < total - 2; j += 4)
	//printf( "%10d,  %10d, %10d，%10d\n",number[j], number[j+1],number[j+2],number[j+3]);

	//printf("==============Serial==============\n");

	//for(int j = 0; j < total - 1; j += 3)
	//		printf( "%6d,  %6d, %6d\n",cc[j], cc[j+1],cc[j+2]);

	//printf("=============Parallel==============\n");

	for(int j = 0; j < total - 1; j += 3)
		printf( "%10d,  %10d, %10d\n",bb[j], bb[j+1],bb[j+2]);
	//FILE* file;
	//if(!(file = fopen("Afterdata.txt","w")))
	//	printf("Open Error!");
	//for(int j = 0; j < total; j++)
	//{
	//	fprintf(file,"%d%c",bb[j],',');
	//}
	return 0;
}