#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DIM 500
#define RADICE_SIZE 10
#define MAX_CIFRE 3

typedef struct list_node *lista_pointer;
typedef struct list_node {
    int chiave[MAX_CIFRE];
    lista_pointer link;
}lista;

void inserzione(int [], int);
void selezione(int[], int);
void scambia(int *, int *);
void quicksort(int [], int, int);
int perno(int [], int, int);
void mergesort(int[], int[], int, int);
void merge(int[], int[], int, int, int);
void adatta(int[], int, int);
void heapsort(int [], int);
lista_pointer radixsort(lista_pointer);

int counter_scambi=0, counter_confronti=0;

int main()
{
    int lista[DIM], i, j;
    int ArrOrd[DIM], ArrInv[DIM], ArrRand[DIM], ArrParz[DIM];
    clock_t start, end;
    double tempo;
    srand(time(NULL));

    for(i=0, j=DIM-1; i<DIM; i++, j--){
        ArrOrd[i]=i;             //da i=0 a 1=size
        ArrInv[i]=j;             //da i=size a i=0
        if(i<(DIM/2))
            ArrParz[i]=i;         //da i=0 sino a i=size/2
        else
            ArrParz[i]=ArrInv[i]; //da i=(size/2)+1 sino i=size inversamente ordinato
        ArrRand[i]=rand()%DIM;   //totalmente random
    }
    start=clock();
    inserzione(ArrOrd, DIM);
    end=clock();
    tempo=(double)(end-start)/(double)CLOCKS_PER_SEC;
    printf("\nArray ordinato:\nNumero confronti: %d\nNumero scambi: %d\nTempo: %f", counter_confronti, counter_scambi, tempo);
    start=clock();
    inserzione(ArrInv, DIM);
    end=clock();
    tempo=(double)(end-start)/(double)CLOCKS_PER_SEC;
    printf("\nArray inversamente ordinato:\nNumero confronti: %d\nNumero scambi: %d\nTempo: %f", counter_confronti, counter_scambi, tempo);
    start=clock();
    inserzione(ArrParz, DIM);
    end=clock();
    tempo=(double)(end-start)/(double)CLOCKS_PER_SEC;
    printf("\nArray parzialmente ordinato:\nNumero confronti: %d\nNumero scambi: %d\nTempo: %f", counter_confronti, counter_scambi, tempo);
    start=clock();
    inserzione(ArrRand, DIM);
    end=clock();
    tempo=(double)(end-start)/(double)CLOCKS_PER_SEC;
    printf("\nArray casuale:\nNumero confronti: %d\nNumero scambi: %d\nTempo: %f", counter_confronti, counter_scambi, tempo);

    return 0;
}

void inserzione(int lista[], int n){
    int i, j, prossimo;

    for (i=0; i<n; i++) {
        prossimo=lista[i];

        if(prossimo>=lista[i-1])
            counter_confronti++;

        for (j=i-1; j>=0 && prossimo < lista[j]; j--){
            lista[j+1]=lista[j];
            counter_confronti++;
            counter_scambi++;
        }
        lista[j+1]=prossimo;
        counter_scambi++;
    }
}