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

void tri_a_bulle(int tab[], int n){
    for(int i = 0; i < n-1; i++){
        for(int j = 0; j < n-1-i; j++){
            if(tab[j] > tab[j+1]){
                int a = tab[j+1];
                tab[j+1] = tab[j];
                tab[j] = a;
            }
        }
    }
}

void tri_insertion(int tab[],int n){
     for(int i = 0; i < n; i++){
         for(int j = 0; j < n-i; j++){
             int ind = j+1;
             while(tab[j]>tab[ind]){
                 int a = tab[ind];
                 tab[ind] = tab[j];
                 tab[j] = a;
                 ind-=1;
             }
         }
    }
}

void tri_par_selection(int tab[] , int n){
    for(int i = 0; i < n; i++){
        int ind_min = i;
         for(int j = 0; j < n; j++){
             if(tab[j]>tab[ind_min]){
                 ind_min = j;   
             }
             int a = tab[ind_min];
             tab[ind_min] = tab[i];
             tab[i] = a;
         }
    }    
}

void interclasser(int a[], int an, int b[], int bn, int res[]) {
    if (an == 0) {
        for (int i = 0; i < bn; i++)
            res[i] = b[i];
        return;
    }
    if (bn == 0) {
        for (int i = 0; i < an; i++)
            res[i] = a[i];
        return;
    }
    if (a[0] <= b[0]) {
        res[0] = a[0];
        interclasser(a + 1, an - 1, b, bn, res + 1);
    } else {
        res[0] = b[0];
        interclasser(a, an, b + 1, bn - 1, res + 1);
    }
}


void tri_fusion(int tab[], int n) {
    if (n <= 1){return;}                

    int milieu = n / 2;
    tri_fusion(tab, milieu);                 
    tri_fusion(tab + milieu, n - milieu);     

    int temp[n];
    interclasser(tab, milieu, tab + milieu, n - milieu, temp);

    for (int i = 0; i < n; i++)
        tab[i] = temp[i];
}


void affiche(int tab[],int n){
    printf("[ ");
    for( int i = 0; i<n ; i++){
        printf("%d ",tab[i]);
    }
    printf("]\n");
}

void affiche_d(double tab[],int n){
    printf("[ ");
    for( int i = 0; i<n ; i++){
        printf("%f ",tab[i]);
    }
    printf("]\n");
}

int *creer_tableau(int n) {
    if (n <= 0) return NULL;
    int *tab = malloc(n * sizeof(int));
    if (tab == NULL) return NULL;
    for (int i = 0; i < n; i++) {
        tab[i] = i;
    }
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1);   /* indice aléatoire entre 0 et i */
        int tmp = tab[i];
        tab[i] = tab[j];
        tab[j] = tmp;
    }
    return tab;
}


int main() {
    
    srand(time(NULL)); 
    int ord[6] = {2,5,10,20,50,100};
    
    int *tab1 = creer_tableau(2);
    int *tab2 = creer_tableau(5);
    int *tab3 = creer_tableau(10);
    int *tab4 = creer_tableau(20);
    int *tab5 = creer_tableau(50);
    int *tab6 = creer_tableau(100);
    int *tab[6] = {tab1, tab2, tab3, tab4, tab5, tab6};


    //-------------------------------------------------------------- tri a bulle -----------------------------------------------------------------
    printf("tri a bulle\n");
    double result_bulle[6];

    for(int i =0 ; i<6 ; i++){
        
        struct timespec t1, t2;
        clock_gettime(CLOCK_MONOTONIC, &t1);
        tri_a_bulle(tab[i],ord[i]);
        clock_gettime(CLOCK_MONOTONIC, &t2);
    
        result_bulle[i] = (t2.tv_sec - t1.tv_sec) + (t2.tv_nsec - t1.tv_nsec) / 1e9;
    }

    affiche_d(result_bulle,6);
    printf("\n");
    
    //-------------------------------------------------------------- tri par insertion -----------------------------------------------------------------
    printf("tri a bulle\n"); 
    double result_inser[6];

    for(int i =0 ; i<6 ; i++){
        
        struct timespec t1, t2;
        clock_gettime(CLOCK_MONOTONIC, &t1);
        tri_insertion(tab[i],ord[i]);
        clock_gettime(CLOCK_MONOTONIC, &t2);
    
        result_inser[i] = (t2.tv_sec - t1.tv_sec) + (t2.tv_nsec - t1.tv_nsec) / 1e9;
    }

    affiche_d(result_inser,6);   
    printf("\n");
    
    //-------------------------------------------------------------- tri par selction -----------------------------------------------------------------
    printf("tri a bulle\n");
    double result_selec[6];

    for(int i =0 ; i<6 ; i++){
        
        struct timespec t1, t2;
        clock_gettime(CLOCK_MONOTONIC, &t1);
        tri_par_selection(tab[i],ord[i]);
        clock_gettime(CLOCK_MONOTONIC, &t2);
    
        result_selec[i] = (t2.tv_sec - t1.tv_sec) + (t2.tv_nsec - t1.tv_nsec) / 1e9;
    }

    affiche_d(result_selec,6);
    printf("\n");
    
//-------------------------------------------------------------- tri fusion -----------------------------------------------------------------
    printf("tri a bulle\n");
    double result_fusion[6];

    for(int i =0 ; i<6 ; i++){
        
        struct timespec t1, t2;
        clock_gettime(CLOCK_MONOTONIC, &t1);
        tri_fusion(tab[i],ord[i]);
        clock_gettime(CLOCK_MONOTONIC, &t2);
    
        result_fusion[i] = (t2.tv_sec - t1.tv_sec) + (t2.tv_nsec - t1.tv_nsec) / 1e9;
    }

    affiche_d(result_fusion,6);
    
    return 0;
}