#include "libr.h"     //incluye la cabecera

int partition (int A[], int p, int r);
void quicksort(int A[], int p, int r);

void heapify(int A[],int i,int last);
void buildheap(int A[],int last);
void heapsort(int A[],int last);

void radixsort(int A[],int last);

                                       	
                                       	/****ESTRUCTURA PRINCIPAL*****/	


 int main(void) {

        int i,j,k,l,d,b;
	int A[10000],B[10000],C[10000];
	long tquick,theap,tradix,sumquick,sumheap,sumradix,sumquick2,sumheap2,sumradix2;

        long promedioquick,promedioheap,promedioradix;
        long x2promedioquick,x2promedioheap,x2promedioradix;
        long DesvEst_quick,DesvEst_heap,DesvEst_radix;

        time_t t;                                         /*definición de estructuras
                                                                para uso de getttimeofday*/
        struct timeval a1,b1;
        struct timeval a2,b2;
        struct timeval a3,b3;

        FILE *fp1,*fp2,*fp3,*fp4;




           	
        fp1= fopen ("Promedios","w");      /*se abren archivos para escritura*/
        fp2= fopen ("Desviaciones","w");
        fp3= fopen ("ploter","w");
        fp4= fopen ("ploter2","w");




        d=Nmax/N;

        if(d<=1)
                b=1;
        else
                b=(int)d;  /* La variable b corresponde al tamaño del paso entre puntos
                                consecutivos de la gráfica,aproxima por el enterosuperior*/



       for(k=b;k<=Nmax;k=k+b){                           //ciclo for que controla la variación del largo del arreglo
   	        sumquick=sumheap=sumradix=sumquick2=sumheap2=sumradix2=0;
   	

		for(i=0; i<itera; i++) {                    // ciclo que controla la repetición de calculo de tiempo para
   						            //obtener un promedio
   		
      			for(j=0; j<k; j++) {                            //llenado de los arreglos A y B
	      			A[j]=(int)(random()/10000000);
	        		C[j]=B[j]=A[j];
	     	   	}	
     	      		/*r(j=0; j<k; j++) {                            //llenado de los arreglos A y B
	      			printf("%d\t%d\t%d\n",A[j],B[j],C[j]);
	        	}*/
                	
	      		gettimeofday(&a1,NULL);                            //toma tiempo inicial para alg. quicksort
			quicksort(A,0,k);        	
			gettimeofday(&b1,NULL);                                                 //segunda toma de tiempo
	      		tquick=((b1.tv_sec-a1.tv_sec)*1000000+(b1.tv_usec-a1.tv_usec));
			sumquick+=tquick;
			sumquick2+=tquick*tquick;
		      	 	  								/*obtención de una variable que almacena el
	      										tiempo total transcurrido en todas las iteraciones*/
     	
	      	
     			gettimeofday(&a2,NULL);                        //lo mismo que antes pero para el alg. heapsort
		     	heapsort(B,k);        	
     			gettimeofday(&b2,NULL);
	     		theap=((b2.tv_sec-a2.tv_sec)*1000000+(b2.tv_usec-a2.tv_usec));
	     	 	sumheap+=theap;
	                sumheap2+=theap*theap;


        	        gettimeofday(&a3,NULL);                        //lo mismo que antes pero para el alg. radixsort
	     		radixsort(C,k);        	
     		 	gettimeofday(&b3,NULL);
		     	tradix=((b3.tv_sec-a3.tv_sec)*1000000+(b3.tv_usec-a3.tv_usec));
		     	sumradix+=tradix;
                	sumradix2+=tradix*tradix;


     	  	
     	 	}
       	
       		promedioquick=(sumquick*0.1)/(itera*0.1);
 		promedioheap=(sumheap*0.1)/(itera*0.1);
		promedioradix=(sumradix*0.1)/(itera*0.1); 	
 	 		
 		x2promedioquick=(sumquick2*0.1)/(itera*0.1);
 		x2promedioheap=(sumheap2*0.1)/(itera*0.1);
		x2promedioradix=(sumradix2*0.1)/(itera*0.1); 	
                		
 		DesvEst_quick=sqrt((double)x2promedioquick-((double)promedioquick*(double)promedioquick));
 		DesvEst_heap=sqrt((double)x2promedioheap-((double)promedioheap*(double)promedioheap));
		DesvEst_radix=sqrt((double)x2promedioradix-((double)promedioradix*(double)promedioradix)); 	
 	
 		
	 	fprintf (fp1,"%d\t%ld\t%ld\t%ld\n",k,promedioquick,promedioheap,promedioradix);      //imprime en archivo los tiempos promedios de los algoritmos
		fprintf (fp2,"%d\t%ld\t%ld\t%ld\n",k,DesvEst_quick,DesvEst_heap,DesvEst_radix);

 	}







   fprintf (fp3,"#Grafica los tiempos promedios de ejecución de los algoritmos de ordenamiento\n");    //escribo en el archivo ploter que entra al gnuplot
   fprintf (fp3,"# Quicksort,Heapsort y Radixsort para N números enteros aleatorios.\n");
   fprintf (fp3," set title \"   Cantidad de enteros aleatorios v/s tiempo. Número de iteraciones: %d\"\n",itera);
   fprintf (fp3," set xlabel \" Cantidad de datos N \"\n");
   fprintf (fp3," set ylabel \" Tiempo en 10E-6[s]\"\n");
   fprintf (fp3," set autoscale\n ");
   fprintf (fp3," set grid\n");
   fprintf (fp3," plot \"Promedios\" using 1:2 title \"QuickSort\" with linespoints 1,\"Promedios\" using 1:3 title \"HeapSort\" with linespoints 2,\"Promedios\" using 1:4 title \"RadixSort\" with linespoints 3 \n");
   fprintf (fp3,"pause -1 \n");

   fprintf (fp4,"#Grafica de las desviaciones estándar de los algoritmos de ordenamiento\n");    //escribo en el archivo ploter que entra al gnuplot
   fprintf (fp4,"# Quicksort,Heapsort y Radixsort para N números enteros aleatorios.\n");
   fprintf (fp4," set title \"   Desv. estándar de los algoritmos v/s tiempo. Número de iteraciones: %d\"\n",itera);
   fprintf (fp4," set xlabel \" Cantidad de datos N \"\n");
   fprintf (fp4," set ylabel \" Tiempo en 10E-6[s]\"\n");
   fprintf (fp4," set autoscale\n ");
   fprintf (fp4," set grid\n");
   fprintf (fp4," plot \"Desviaciones\" using 1:2 title \"Desv.QuickSort\" with linespoints 1,\"Desviaciones\" using 1:3 title \"Desv.HeapSort\" with linespoints 2,\"Desviaciones\" using 1:4 title \"Desv.RadixSort\" with linespoints 3 \n");
   fprintf (fp4,"pause -1 \n");



   fclose(fp1);
   fclose(fp2);
   fclose(fp3);
   fclose(fp4);


   printf("\nMostrando el gráfico de promedios:\n");
   printf("Presione ENTER para ver la siguiente gráfica\n");
   system("gnuplot ploter");   //llamado a gnuplot para que grafique los datos

   printf("\nMostrando el gráfico de las desviaciones estándar:\n");
   printf("Presione ENTER para terminar\n");
   system("gnuplot ploter2");   //llamado a gnuplot para que grafique los datos


   return 0;

   }