qs.cpp

本人写的一个快速排序的程序

//为什么在debug的时候总是会出现几次并行的时间比串行的长的情况呢？
#include<stdio.h>
#include <omp.h>
#include <stdlib.h>
#include<windows.h>
#define N 200
#define NUM_THREADS 2 

int rand(void);

int partition(int b[],int,int);
void parallelquicksort(int b[],int,int);
void serialquicksort(int b[], int ,int );

void main()
{
	int a[N],quicks[N];
	/*omp_set_num_threads(NUM_THREADS);*/
	

#pragma omp parallel for
		for(int i = 0;i< N; i++)
		{
			a[i]=rand()%200;
			quicks[i] = a[i];
			/*printf("a[%d] = %4d   ",i,a[i]);*/
		}
	LARGE_INTEGER freq, t0, t1;
	QueryPerformanceFrequency(&freq);
	QueryPerformanceCounter(&t0);

	parallelquicksort(a,1,N-1);

	QueryPerformanceCounter(&t1);
	printf("Serial time is %d ms\n",((t1.QuadPart - t0.QuadPart)*1000000) /freq.QuadPart);

	QueryPerformanceCounter(&t0);

	parallelquicksort(quicks,1,N-1);

	QueryPerformanceCounter(&t1);
	printf("Parallel time is %d ms\n",((t1.QuadPart - t0.QuadPart)*1000000) /freq.QuadPart);

	for(int i = 1;i < N; i++)
	{
		printf("%10d",quicks[i]);
	}
	printf("\n");
	for(int i = 1;i < N; i++)
	{
		printf("%10d",a[i]);
	}
}

//#pragma omp parallel 

void serialquicksort(int r[], int s,int t )
{
	int i;
	if(s < t)
	{
		i = partition(r,s,t);
		serialquicksort(r,s,i-1);
		serialquicksort(r,i+1,t);
	}
}


void parallelquicksort(int r[], int s,int t){
	int i;
	if(s<t){
		i=partition(r,s,t);
#pragma omp parallel sections   
		{    
#pragma omp section  
			{
				parallelquicksort(r,s,i-1);
			}
#pragma omp section 
			{
				parallelquicksort(r,i+1,t);
			}
		}
	}
}


int partition(int r[],int low,int high)
{
	r[0]=r[low];
	while(low<high)
	{
		while(low<high&&r[0]<r[high]) 
			high--;
		if(low<high)
		{
			r[low]=r[high];
			low++;
		}
		while(low<high&&r[0]>r[low]) 
			low++;
		if(low<high){
			r[high]=r[low];
			high--;
		}

	}
	r[low]=r[0];
	return low;
}