in_tmp.c

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

#include <stdio.h>
#include <unistd.h>
#include <time.h>
#include <math.h>
#include <unistd.h>
#include <time.h>
#define TO_MSEC(x)      (1000*(x)/CLOCKS_PER_SEC)
#define MAX_ARRAY_LENGTH 100000000
#define VERSION          1
#define RAND_RANGE_MAX   500000
double seed;
int calcolaprecisione();
int getrip(int n,int precisione);
double tempoinsertion(int A[],int la,int rip);
void    insort (int array[],int length);
void    sort(int A[], int min, int max);
int     merge(int A[], int p, int q,int r);
//Funzioni veramente rudimentali per l'i/o
void readArray(int A[], int n);
void printArray(int A[], int n);
//void int_insertion(int n,long x,int R);
//Funzioni per il random;
void update_seed();
double l_rand_alg();
void med_sort(int larray,int ncampioni);
void int_insertion(int n,long x,int R);
double tempoinsertion(int A[],int la,int rip);
int l_int_rand(int n);
void randArray(int A[],int range_random,int length_array,int randomize);
void printArray(int A[], int n);
void copy_array(int a[],int b[],int la,int lb);
void med_insort(int larray,int ncampioni,int alg);
void times (int larray,int ncampioni);
void mergeAB(int c[],int a[], int N,int b[],int M);
void optimizationAB(int a[],int l,int r);
void optimizationABr(int a[],int b[],int l,int r);
void mad_optimus(int larray,int ncampioni);

int main()
{
mad_optimus(20,500);
}

void times (int larray,int ncampioni){
	int progress=0,k,l,i,m;
	int tmp[larray];
	double tnetto,tlordo,tmedio,ttara,varianza;
	double s1=0,s2=0,rip,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);
 	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%g,%g,%g,%g,%g",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);
        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 optimus \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);}

void mergeAB(int c[],int a[], int N,int b[],int M) {
int i,j,k;
for (i=0,j=0,k=0;k<N+M;k++) 
{
  if (i==N) { c[k]= b[j++]; continue; }
  if (j==M) {  c[k]= a[i++]; continue; }
 c[k]= (a[j]<b[j]) ? a[i++]: b[j++] ; }}

void optimizationAB(int a[],int l,int r) {
 int i,aux[r];
 for (i=0;i<=r;i++) aux[i]=a[i];
 optimizationABr(a,aux,l,r);}

void optimizationABr(int a[],int b[],int l,int r)
{
 int m=(l+r)/2;
 if ((r-1)<=10){ insort(a,r); return; }
 optimizationABr(b,a,l,m);
 optimizationABr(b,a,m+1,r);
 mergeAB(a+1,b+1,m-1+1,b+m+1,r-m); }


void med_insort(int larray,int ncampioni,int alg){
        int a[larray],temp[larray];
        clock_t t1=0,t2=0;
        double I_C,delta,tlordo,ttara,tnetto,tmedio,varianza,s1=0,s2=0;
        int rip=0,k,i,l,z;
        randArray(a,500,larray,0);
        rip=getrip(larray,5);
        for(l=0;l<larray;l++)a[l]=temp[l];
        for(k=0;k<ncampioni;k++){
                randArray(a,500,larray,0);
                t1=clock();
                        for(i=0;i<rip;i++){
                                randArray(temp,500,larray,0);
                              if(alg=0)  	 insort(temp,larray);
                              else if (alg=1)   sort(temp,0,larray);                }
                        t2=clock();
                        tlordo=TO_MSEC(t2-t1);
                        t1=clock();
                        for(k=0;k<ncampioni;k++) {randArray(temp,500,larray,0);
					          if (alg=0)z=2;
						  else if (alg=1)z=2; }
                        t2=clock();
                        ttara=TO_MSEC(t2-t1);
                        tnetto=((tlordo-ttara)/rip)/1000;
                        s1+=tnetto;
                        s2+=tnetto;}
                        tmedio=s2/ncampioni; //non e chiaro da qui in poi;
                        varianza=(s1-ncampioni*tmedio*tmedio)/(ncampioni-1) ;
                        delta=1.96*sqrt(varianza/ncampioni);
			I_C=tmedio-(delta*tmedio)+delta;
			printf ("Lunghezza = %d ripetizioni %d ",larray, rip);
                        printf ("\nMedia = %g Varianza : %g Delta :%g",tmedio,varianza,delta);
                        printf ("\nIntervallo di Confidenza =%g \n",I_C);
}

void med_sort(int larray,int ncampioni){
        int a[larray],temp[larray];
        clock_t t1=0,t2=0;
        double I_C,delta,tlordo,ttara,tnetto,tmedio,varianza,s1=0,s2=0;
        int rip=0,k,i,l,z;
        randArray(a,500,larray,0);
        rip=getrip(larray,5);
        for(l=0;l<larray;l++)a[l]=temp[l];
        for(k=0;k<ncampioni;k++){
                randArray(a,500,larray,0);
                t1=clock();
                        for(i=0;i<rip;i++){
                                randArray(temp,500,larray,0);
                                sort(temp,0,larray);                }   
                        t2=clock();
                        tlordo=TO_MSEC(t2-t1);
                        t1=clock();
                        for(k=0;k<ncampioni;k++) randArray(temp,500,larray,0);
                        t2=clock();
                        ttara=TO_MSEC(t2-t1);
                        tnetto=((tlordo-ttara)/rip)/1000;
                        s1+=tnetto;
                        s2+=tnetto;}
                        tmedio=s2/ncampioni; //non e chiaro da qui in poi;
                        varianza=(s1-ncampioni*tmedio*tmedio)/(ncampioni-1) ;
                        delta=1.96*sqrt(varianza/ncampioni);
                        I_C=tmedio-(delta*tmedio)+delta;
                        printf ("Lunghezza = %d ripetizioni %d ",larray, rip);
                        printf ("\nMedia = %g Varianza : %g Delta :%g",tmedio,varianza,delta);
                        printf ("\nIntervallo di Confidenza =%g \n",I_C);
}

		/*	tmedio=s2/ncampioni;
			varianza=(s1-ncampioni*tmedio*tmedio)/(ncampioni-1);
			printf ("\nLunghezza = %d ripetizioni %d ",larray, rip);
			printf ("\nMedia = %g Varianza : %g",tmedio,varianza);
			printf ("\nDelta =%g  ,Intervallo di confidenza : %g",1.96*sqrt(varianza/ncampioni),tmedio-(1.96*sqrt(varianza/ncampioni)));
}*/

void int_insertion(int n,long x,int R){
int C=500;
int rip;
int temp[n],a[n],i,l;
double tempoins=0,sommatoria=0,sommatoria2=0,delta=0,S=0,media=0;
randArray(a,R,n,1);
rip=getrip(n,5);
printf ("%d\n",rip);
for (i=0;i<C;i++){
 //    randArray(temp,R,n);
     for (l=0;l<n;l++)a[l]=temp[l];
     tempoins=tempoinsertion(temp,n,rip);
     sommatoria +=tempoins;
     sommatoria2+=sqrt(tempoins);
 // printf ("%f\n",tempoins);
//  printf ("%f sommatoria,%f sommatoria2\n",sommatoria,sommatoria2);
	}
media=sommatoria/(C*rip);
S=sqrt( (sommatoria2/(C*(rip*rip)))     -((media*media) ));//square