[openMP] QuickSort 병렬화

 

#include 
#include 
#include 

void setup( int* array, int len )
{
	int i = 0;
	#pragma omp parallel for
	for(i=0; i<len; i++)
	{
		array[i] = (i*7-3224) ^ 20435;
	}	
}

void quick_sort_range(int *array, int lower, int upper)
{
	int tmp;
	int mid = (upper + lower) / 2;
	int pivot = array[mid];
	int tlower = lower, tupper = upper;

	
	while( tlower <= tupper )
	{
		while(array[tlower] < pivot) { tlower++; }
		while(array[tupper] > pivot) { tupper--; }
		
		if( tlower <= tupper )
		{
			tmp = array[tlower];
			array[tlower] = array[tupper];
			array[tupper] = tmp;
			tupper--;
			tlower++;
		}
	
	}
	

	#pragma omp task shared(array) firstprivate(lower, tupper)
	if( lower < tupper )
	{
		quick_sort_range(array, lower, tupper); 
	}
	
	#pragma omp task shared(array) firstprivate(tlower, upper)
	if( tlower < upper )
	{
		quick_sort_range(array, tlower, upper); 
	}

}

int main()
{
	double before = omp_get_wtime();

	int size = 10*1024*1024;
	int *array = (int*)malloc(sizeof(int)*size);
	setup(array, size);
	
	#pragma omp parallel shared(array) private(size)
	{
		#pragma omp single nowait
		{
			quick_sort_range(array, 0, size-1);

		}
	}

	printf("%f sec qSort Complete.\n",omp_get_wtime()-before);

	return 0;
}