#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <limits.h>

/* USATE LE VOSTRE COSTANTI AL POSTO DI QUELLE INDICATE*/

#define N 5000               // dimensione massima dell'array da ordinare
#define STEP 100            // gap tra due esperimenti successivi
#define NUMEXP 100            // numero di volte che un esperimento di una certa dimensione si ripete


void InsertionSort(int *, int );
void MergeSort(int *,int,int);
void Merge(int *,int,int,int);
void GeneraVettore(int *,int);  // genera un vettore casuale di una determinata dimensione
void IbridoMergeSort(int *,int,int,int); // merge sort ibrido con insertion sort
void CopiaVettore(int *,int *,int);  // copia un vettore in un altro

int main()
{
	clock_t start, end; // variabili per la tempistica
	int dimensione;     // dimensione del vettore attuale durante l'esperimento
	int iterazione;     // indice dell'iterazione durante l'esperimento
	int limite_ibrido;  // risultato della prima parte di questo esercizio
	int* vettore;
	int *vettore_copia; // variabili per mantenere il vettore da ordinare
	double IS,MS,IMS; // variabili per mantenere la sommma dei tempi dei tre algoritmi
	double mediaIS,mediaMS,mediaIMS; // variabili per le medie dei tempi (al variare dell'iterazione)
    FILE *risultati;

    srand(1);         // seme per i numeri casuali (NON USARE 'time')

    vettore = malloc(sizeof(int)*N);
    vettore_copia = malloc(sizeof(int)*N);


	risultati=fopen("risultati_parte_seconda_esercizio1.txt","w");
	if (risultati==NULL)
	{
        printf ("ERRORE nell'apertura del file");
        return(1);
	}

    printf ("Inserisci il limite insertion sort VS merge sort: ");
    scanf ("%d", &limite_ibrido);
    printf ("Dim\t Insertion\t Merge\t\t Hybrid\n");



    for(dimensione=STEP;dimensione<=N;dimensione+=STEP)
    {
        IS = 0;
        MS = 0;
        IMS = 0;
        for (iterazione = 1; iterazione <= NUMEXP; iterazione++)
        {
            GeneraVettore(vettore,dimensione);
            CopiaVettore(vettore,vettore_copia,dimensione);
            start = clock();
            InsertionSort(vettore,dimensione);
            end = clock();
		    IS = IS + (double)(end-start)/CLOCKS_PER_SEC;

		    CopiaVettore(vettore_copia,vettore,dimensione);

		    start = clock();
            MergeSort(vettore,0,dimensione-1);
            end = clock();
		    MS = MS + (double)(end-start)/CLOCKS_PER_SEC;

		    CopiaVettore(vettore_copia,vettore,dimensione);

		    start = clock();
            IbridoMergeSort(vettore,0,dimensione-1,limite_ibrido);
            end= clock();
		    IMS = IMS + (double)(end-start)/CLOCKS_PER_SEC;

        }
        mediaIS=IS/NUMEXP;
		mediaMS=MS/NUMEXP;
		mediaIMS=IMS/NUMEXP;

        printf ("%d\t %f\t %f\t %f\n",dimensione,mediaIS,mediaMS,mediaIMS);
        fprintf(risultati,"%d\t %f\t %f\t %f\n",dimensione,mediaIS,mediaMS,mediaIMS);
    }
    fclose(risultati);

}

void RangedInsertionSort(int* vettore, int sx, int dx){
	int i,j;
  	for(i=sx; i<dx; i++){
    	int key= vettore[i];
   		j=i-1;
   		while(j>=sx && vettore[j]>key){
   			vettore[j+1]=vettore[j];
   			j=j-1;
			}
		vettore[j+1]=key;
	}
	return;
}

void IbridoMergeSort(int *vettore,int sx,int dx,int limite)
{
    /* costruire questa funzione */
    if(sx<dx){
    	int centro= (sx+dx)/2;
    	if((dx-sx)<=limite){
    		RangedInsertionSort(vettore,sx,dx);
		}else{
			IbridoMergeSort(vettore,sx,centro,limite);
			IbridoMergeSort(vettore,centro+1,dx,limite);
			Merge(vettore,sx,centro,dx);
		}
	}
	return;
}

void InsertionSort(int *vettore, int dimensione)
{
    /* fare questa funzione */
    int i,j;
    for(i=1; i<dimensione; i++){
    	int key= vettore[i];
    	j=i-1;
    	while(j>=0 && vettore[j]>key){
    		vettore[j+1]=vettore[j];
    		j=j-1;
		}
		vettore[j+1]=key;
	}

    return;
}



void MergeSort(int *vettore,int sx,int dx)
{
	/* fare questa funzione */
	if(sx<dx){
		int centro= (sx+dx)/2;
		MergeSort(vettore,sx,centro);
		MergeSort(vettore,centro+1,dx);
		Merge(vettore,sx,centro,dx);
	}
    return;
}

void Merge(int *vettore,int sx,int centro,int dx)
{
	/* fare questa funzione */
	int i=sx;
	int k=0;
	int j= centro+1;
	int* b;
	b=(malloc(sizeof(int)*(dx-sx+1)));
	while(i<centro && j<= dx){
		if(vettore[i]<=vettore[j]){
			b[k]=vettore[i];
			i++;
		}else{
			b[k]=vettore[j];
			j++;
		}
		k++;
	}
	while(i<=centro){
		b[k]=vettore[i];
		i++;
		k++;
	}
	while(j<=dx){
		b[k]=vettore[j];
		j++;
		k++;
	}
	for(k=sx; k< dx; k++)
		vettore[k]=b[k-sx];

    return;
}

void GeneraVettore(int *vettore, int dimensione)
{
	int i;
	int casuale;

	for(i=0;i<dimensione;i++)
	{
		casuale=rand() % dimensione;
		vettore[i]=casuale;
	}
}

void CopiaVettore(int *vettore_origine, int *vettore_destinazione, int dimensione)
{
    int i;

    for (i=0;i<dimensione;i++)
    {
        vettore_destinazione[i]=vettore_origine[i];
    }
}