time.c

A order algoritm comparison by the C time(). Comparison beetwen : insort,selection sort,mergesort,

#include "in.h"
#include "func.h"

/*-------------------------------------------------------------------
 * Function: calculateprecision
 * Purpose : Calculate the precision of the processor
 */

int calculateprecision()
{
 int a=0;
 double end=0;
 clock_t start =  clock();
 clock_t stop = start;
 while (( end =TO_MSEC(stop-start))==0)
  {
  a++;
  stop =clock();
  }
return (int)end;
}

/*------------------------------------------------------------------- 
 * Function: getrip
 * Purpose : Calculate the (int) ripetition to stimate the times with
 *           an error of precisione
 * Input args :n the length of the array to stimate
 *             precisione : the error to tollerate     
 *           
 */ 
int getrip(int n,int precisione ){ 

double delta = (100*(double)calculateprecision())/(double)precisione ;  
int A[n];
clock_t t1=0,t2=0;
double r=1,a,b;
int j,i,m;

randArray(A,500,n,1);
        while (TO_MSEC(t2-t1)<delta)
        {
        r=r*2;
        t1=clock();       
        for(i=1;i<r;i++) randArray(A,500,n,1);
        t2=clock();
        }
a=(int)(r/2);
b=r;
while((b-a)>=5)
        {
        r=((a+b)/2);
        t1=clock();
        for(i=1;i<r;i++) randArray(A,500,n,1);
        t2=clock();
        if(TO_MSEC(t2-t1)<=delta)
        a=r;
        else b=r;
}  
return (int)r;
}

/*-------------------------------------------------------------------
 * Function: mad_sort
 * Purpose : The function is the core of lasd it stimates the medium time
 *           for the algoritm to reorder an array of larray length
 *           on ncampioni numer of tests.(this is for mergesort)
 * Input args :larray the length of the array to stimate
 *	       ncampioni the numer of arrays to stimate
 */

void mad_sort(int larray,int ncampioni){
	int progress=0,k,rip,l,i,m;
	int tmp[larray];
	double tnetto,tlordo,tmedio,ttara,varianza;
	double s1=0,s2=0,delta,I_Cmin,I_Cmag;
	rip=getrip(larray,5);
	for (k=0;k<ncampioni;k++) {
		double time1,time2;
		int a [larray];
//		printf ("%d\n",k);
		randArray (a,5000,larray,1);
		progress = (int)k*100/500;
		time1=clock();
		for (i=0;i<rip;i++){
		//printf ("%d\n",i);
			randArray (a,5,larray,1);
			sort(a,0,larray);
		}
		 time2=clock();
		 tlordo=TO_MSEC(time2 - time1);
 	time1=clock();
	for (m=0;m<larray;m++)tmp[m]=a[m];
       	for(i=0; i<rip; i++ ) randArray (tmp,5,larray,1);
	time2=clock();
	ttara=TO_MSEC(time2 - time1);
	tnetto=(tlordo-ttara)/rip;
	s1+=tnetto*tnetto;
	s2+=tnetto;
	}
	tmedio=s2/ncampioni;
	varianza=(s1/ncampioni)-(tmedio*tmedio);
	delta=1.96*sqrt(varianza/ncampioni);
	I_Cmin=tmedio-delta;
	I_Cmag=tmedio+delta;
printf ("\n[*] Results for merging \n"
          "[*] Details : length array :%d, Number of test to reorder %d, Num of rips %d   \n"
          "[*]           Medium time : %g, Varianza : %g, Delta :%g  \n"
          "[*]           Confidence interval [%g , %g]\n",larray,ncampioni,rip,tmedio,varianza,delta, I_Cmin,I_Cmag);}


/*-------------------------------------------------------------------
 * Function: mad_insort
 * Purpose : The function is the core of lasd it stimates the medium time
 *           for the algoritm to reorder an array of larray length
 *           on ncampioni numer of tests.(this is for insertion sort)
 * Input args :larray the length of the array to stimate
 *             ncampioni the numer of arrays to stimate
 */
void mad_insort(int larray,int ncampioni){
	int progress=0,k,l,i,m,rip;
	int tmp[larray];
	double tnetto,tlordo,tmedio,ttara,varianza;
	double s1=0,s2=0,delta,I_Cmin,I_Cmag;
	rip=getrip(larray,5);
	for (k=0;k<ncampioni;k++) {
		double time1,time2;
		int a [larray];
//		printf ("%d\n",k);
		randArray (a,5000,larray,1);
		progress = (int)k*100/500;
		time1=clock();
		for (i=0;i<rip;i++){
		//printf ("%d\n",i);
			randArray (a,5,larray,1);
			insort(a,larray);
		}
		 time2=clock();
		 tlordo=TO_MSEC(time2 - time1);
 	 for (m=0;m<larray;m++)tmp[m]=a[m];
		 
	time1=clock();
       	for(i=0; i<rip; i++ ) randArray (tmp,5,larray,1);
	time2=clock();
	ttara=TO_MSEC(time2 - time1);
	tnetto=(tlordo-ttara)/rip;
	s1+=tnetto*tnetto;
	s2+=tnetto;
	}
	tmedio=s2/ncampioni;
	varianza=(s1/ncampioni)-(tmedio*tmedio);
	
	delta=1.96*sqrt(varianza/ncampioni);
	I_Cmin=tmedio-delta;
	I_Cmag=tmedio+delta;
printf ("\n[*] Results for Insertion sort \n"
          "[*] Details : length array :%d, Number of test to reorder %d, Number of rips %d\n"
          "[*]           Medium time : %g, Varianza : %g, Delta :%g  \n"
          "[*]           Confidence interval [%g , %g]\n",larray,ncampioni,rip,tmedio,varianza,delta
, I_Cmin,I_Cmag);}


void mad_optimus(int larray,int ncampioni){
        int progress=0,k,rip,l,i,m;
        int tmp[larray];
        double tnetto,tlordo,tmedio,ttara,varianza;
        double s1=0,s2=0,delta,I_Cmin,I_Cmag;
        rip=getrip(larray,5);
        for (k=0;k<ncampioni;k++) {
                double time1,time2;
                int a [larray];
//              printf ("%d\n",k);
                randArray (a,5000,larray,1);
                progress = (int)k*100/500;
                time1=clock();
                for (i=0;i<rip;i++){
                //printf ("%d\n",i);
                        randArray (a,5,larray,1);
                        optimizationAB(a,0,larray);
                }
                 time2=clock();
                 tlordo=TO_MSEC(time2 - time1);
         for (m=0;m<larray;m++)tmp[m]=a[m];
	time1=clock();
        for(i=0; i<rip; i++ ) randArray (tmp,5,larray,1);
        time2=clock();
        ttara=TO_MSEC(time2 - time1);
        tnetto=(tlordo-ttara)/rip;
        s1+=tnetto*tnetto;
        s2+=tnetto;
        }
        tmedio=s2/ncampioni;
        varianza=(s1/ncampioni)-(tmedio*tmedio);
        delta=1.96*sqrt(varianza/ncampioni);
        I_Cmin=tmedio-delta;
        I_Cmag=tmedio+delta;
printf ("\n[*] Results for optim\n"
          "[*] Details : length array :%d, Number of test to reorder %d, Num of rips %d   \n"
          "[*]           Medium time : %g, Varianza : %g, Delta :%g  \n"
          "[*]           Confidence interval [%g , %g]\n",larray,ncampioni,rip,tmedio,varianza,delta
, I_Cmin,I_Cmag);}