/***************************************************************************************************
|   Program:		orderingMain.c																   |
|   Description:	use dterministic and randermised algorithm to find k-th largest elements of an |
|					unsorted list, and record average running time (for each n and k run 10 times  | 
|                   to get the average) with each algorithm										   |
|   Arthurs:		Shanying Zhang, Shuo Yang, Xiangdong Wen 									   |
|   time:			May, 2002																	   |
***************************************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include "quickSortDeterm.h"

main()
{

	int i, j, x, size, k, temp, k_largest, numRuns =10;
	double duration, sumDetermDurn=0.0, avgDetermDurn=0.0, sumRandDurn=0.0, avgRandDurn=0.0;
    clock_t start, finish;
	int* buf, *buf1;
    FILE *fpDeterm= NULL, *fpRand=NULL;
	
	
	if((fpDeterm = fopen("outputDeterm.txt", "a"))==NULL)
		printf("\ncannot open output file\n");
	if((fpRand = fopen("outputRand.txt", "a"))==NULL)
		printf("\ncannot open output file\n");

	fprintf(fpDeterm, "\n********************** Result using deterministic algorithm **********************\n\n");
	fprintf(fpDeterm, "\n\t\tn\t\tk\t\tT(Sec)\t\t\tnlogn\n");
//	fprintf(fpDeterm, "\n\t\tn\t\tk\t\tT(Sec)\n");
	fprintf(fpRand, "\n**********************    Result using randomized algorithm   **********************\n\n");
	fprintf(fpRand, "\n\t\tn\t\tk\t\tT(Sec)\t\t\tnlogn\n");
//	fprintf(fpRand, "\n\t\tn\t\tk\t\tT\n");
	
	/*set seed for rand()*/
	srand( (unsigned)time( NULL ) );
//	for(size=1000000; size<=1000000; size*=10){
	for(x=0, size=1000; size<=1000000; x++, size=x*5000){

		printf("\n\nsize = %d\nk=", size);
		for(k=3*size/4; k<=3*size/4; k++){
//		for(x=0, k=1; k<=size; x++, k=1000*x){
			printf("%d\t", k);
			sumDetermDurn=0.0; 
			avgDetermDurn=0.0; 
			sumRandDurn=0.0; 
			avgRandDurn=0.0;
			for(i=1; i<=numRuns; i++){

				/*initialize two same unordered list of numbers randomly*/
				buf = malloc(sizeof(int)*(size+1));
				buf1 = malloc(sizeof(int)*(size+1));
				buf[0]=0;
				buf1[0]=0;
				for(j=1; j<=size; j++){
					temp = rand() % 10000;
					buf[j] = temp;
					buf1[j] = temp;
				}
		
				/*print the initial list, for debug only*/
/*				fprintf(fpDeterm, "\nthe randomly generated list of numbers are:\n\n");
				for(j=1; j<=size; j++)
					fprintf(fpDeterm,"%d\t", buf[j]);*/
		
				/*use randomized quickSort to sort and thus deterministiclly find the k-th largest
				element, record the computing time*/
				start = clock();
				randomizedQuickSort(buf, 1, size);
				finish = clock();
				duration = (double)(finish - start) / CLOCKS_PER_SEC;
//				fprintf(fpDeterm, "\nduration using deterministic method: %2.6f seconds\n", duration );
				sumDetermDurn += duration;
		
				/*print the ordered list, for debug only*/
/*				fprintf(fpDeterm, "\n\nthe list of numbers sorted using randamized quickSort are:\n\n");
				for(j=1; j<=size; j++)
					fprintf(fpDeterm,"%d\t", buf[j]);
				fprintf(fpDeterm, "\n\nthe K-th largest element found with deterministic method is %d\n", buf[k]);*/
				free(buf);

				/*use randomized algorithm to find k-th largest element*/
				start = clock();
				k_largest=randomizedSelect(buf1, 1, size, k);
				finish = clock();
				duration = (double)(finish - start) / CLOCKS_PER_SEC;
//				fprintf(fpDeterm, "\nduration using randomized method: %2.6f seconds\n", duration );
				sumRandDurn += duration;

				/*print the semi-ordered list using randomized method, for debug only*/
/*				fprintf(fpDeterm, "\n\nthe list of numbers after using randamized method are:\n\n");
				for(j=1; j<=size; j++)
					fprintf(fpDeterm,"%d\t", buf1[j]);
				fprintf(fpDeterm, "\n\nthe K-th largest element found with deterministic method is %d\n", k_largest);*/
				free(buf1);
			}
	
			avgDetermDurn = sumDetermDurn/numRuns;
			fprintf(fpDeterm, "\n\t\t%d\t\t%d\t\t%2.6f\t\t%0.2f", size, k, avgDetermDurn, size*log(size) );
//			fprintf(fpDeterm, "\n\t\t%d\t\t%d\t\t%2.6f", size, k, avgDetermDurn );
			avgRandDurn = sumRandDurn/numRuns;
			fprintf(fpRand, "\n\t\t%d\t\t%d\t\t%2.6f\t\t%0.2f", size, k, avgRandDurn, size*log(size) );
//			fprintf(fpRand, "\n\t\t%d\t\t%d\t\t%2.6f", size, k, avgRandDurn );
		}
	}
	
	fclose(fpDeterm);
	fclose(fpRand);
}