/* qs4.c SJ */

/*
 * 15. Parallelize the standard Quicksort using OpenMP. It is enough to parallelize the two recursive
calls. You can either use #sections or make a parallel loop of two iterations. Notice, that
there is no use to try to execute recursive calls in parallel if we have run out of threads.

 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>
#include <omp.h>

/* 

   Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz
   (quad)

Sequential, N=1000000, time = 0.071948 s, 13.899 Melem/s
Parallel, N=1000000, time = 0.036984 s,  27.04 Melem/s
Speedup   1.95, P = 4, efficiency = 0.49

Sequential, N=10000000, time = 0.834032 s, 11.990 Melem/s
Parallel, N=10000000, time = 0.346496 s,  28.86 Melem/s
Speedup   2.41, P = 4, efficiency = 0.60

Sequential, N=100000000, time = 9.489152 s, 10.538 Melem/s
Parallel, N=100000000, time = 3.087855 s,  32.38 Melem/s
Speedup   3.07, P = 4, efficiency = 0.77

*/



void quicksort_seq(int *A, int N);
void quicksort_r(int *A, int first, int last);
void quicksort_par(int *A, int N);
int partition(int *A, int first, int last);
void generateinput(int **A, int N);
double ltime();
int checkresult(int *A, int N);


int main(int argc, char *argv[]) {
	int N = 10000000;
	int *A = NULL;
	int P = 1;
	double starttime, endtime, seqtime, partime;

	if (argc > 1)
		N = atoi(argv[1]);

	P = omp_get_num_procs();
	omp_set_num_threads(16);

	generateinput(&A, N);
	starttime = ltime();
	quicksort_seq(A, N);
	endtime = ltime();
	seqtime = endtime-starttime;
	printf("Sequential, N=%d, time = %.6lf s, %6.3lf Melem/s\n", N,
		   seqtime, (N/seqtime)/1000000);
	if (! checkresult(A, N))
		printf("Wrong result");
	free(A);

	generateinput(&A, N);
	starttime = ltime();
	quicksort_par(A, N);
	endtime = ltime();
	partime = endtime-starttime;
	printf("Parallel, N=%d, time = %.6lf s, %6.2lf Melem/s\n", N,
		   partime, (N/partime)/1000000);
	printf("Speedup %6.2f, P = %d, efficiency = %4.2f\n", seqtime/partime, P,
		   (seqtime/partime)/P);
	if (! checkresult(A, N))
		printf("Wrong result");
	free(A);

	return 0;

} // main() 

void generateinput(int **A, int N) {
	int i;
	*A = (int*)malloc(N*sizeof(int));
	for(i = 0; i < N; i++) {
		(*A)[i] = rand() % N*20;
	}
}

int checkresult(int *A, int N) {
	int i;
	for (i = 0; i < N-1; i++)
		if (A[i] > A[i+1])
			return 0;
	return 1;
}





/* sequential version */
/* wrapper to sort N elements of array A */
void quicksort_seq(int *A, int N) {
	quicksort_r(A, 0, N-1);
}

/* main sequential recursive quicksort */
void quicksort_r(int *A, int first, int last) {
	if (first < last) {
		int middle = partition(A, first, last);
		quicksort_r(A, first, middle-1);
		quicksort_r(A, middle+1, last);
	}
}

/* parallel version */
/* wrapper to sort N elements of array A */
void quicksort_par(int *A, int N) {

    // TODO, call parallel versoin instead of sequential
	quicksort_r(A, 0, N-1);
}


int partition(int *A, int first, int last) {

	int middle, pivot_i, pivot;

	// median of 1st, middle and last
	middle = (last-first)/2;
	if (A[first] < A[middle]) {
		if (A[middle] < A[last])
			pivot_i = middle;
		else if (A[first] < A[last])
			pivot_i = last;
		else
			pivot_i = first;
	} else {
		if (A[first] < A[last])
			pivot_i = first;
		else if (A[middle] < A[last])
			pivot_i = last;
		else
			pivot_i = middle;
	}

	// save pivot, empty first
	pivot = A[pivot_i];
	A[pivot_i] = A[first];

	// main partition

	while (first < last) {
		while ((first < last) && pivot <= A[last])
			last--;
		A[first] = A[last];
		while((first < last) && pivot >= A[first])
			first++;
		A[last] = A[first];
	} // while
	A[first] = pivot;
	return first;
}


double ltime()
{
    return omp_get_wtime();
}