#include <time.h>

#include <stdbool.h>

#include <stdio.h>

#include <stdlib.h>

#include <unistd.h>



void generertableaualeatoire(int *tab, int n){

    int i = 0;



    srand((unsigned)time(NULL));

    for (i = 0; i < n; i++){

        tab[i] = (rand() % 100);

    }

}



void affichertableau(int *tab, int n){

    int i = 0;



    printf("  - Mon tableau contient : [");

    for (i = 0; i < n; i++){

        printf("%i;", tab[i]);

    }

    printf("]\n");

}



void permute(int *taba, int *tabb){

    int temp;

    temp = *taba;

    *taba = *tabb;

    *tabb = temp;

}



void tri_selection(int *tabval, int n){

    int i, j, min;



    for (i = 0; i < (n-1); i++){

        min = i;

        for (j = i+1; j < n; j++){

            if (tabval[j] < tabval[min]){

                min = j;

            }

        }

        permute(&tabval[i], &tabval[min]);

    }

}



void tri_insertion(int *tabval, int n){

    int i,p,j;

    int x;



    for (i = 0; i < n; i++){

       x = tabval[i];

       p = i-1;

       while (tabval[p] > x && p-- > 0) {}

       p++;

       for (j = i-1; j >= p; j--){

           tabval[j+1] = tabval[j];

       }

       tabval[p] = x;

    }

}



void tri_bulle(int *tabval, int n){

    int i;

    bool permutation;

    do{

        permutation = false;

        for(i=0; i<n-1; i++){

            if(tabval[i]>tabval[i+1]){

                permute(&tabval[i], &tabval[i+1]);

                permutation = true ;

            }

        }

        n--;

    }

    while(permutation);

}



void fusion(int tableau[],int deb1,int fin1,int fin2){

    int *table1;

    int deb2=fin1+1;

    int compt1=deb1;

    int compt2=deb2;

    int i;



    table1=malloc((fin1-deb1+1)*sizeof(int));



    for(i=deb1;i<=fin1;i++){

        table1[i-deb1]=tableau[i];

    }



    for(i=deb1;i<=fin2;i++){

        if (compt1==deb2){

            break;

        }

        else if (compt2==(fin2+1)){

            tableau[i]=table1[compt1-deb1];

            compt1++;

        }

        else if (table1[compt1-deb1]<tableau[compt2]){

            tableau[i]=table1[compt1-deb1];

            compt1++;

        }

        else{

            tableau[i]=tableau[compt2];

            compt2++;

        }

    }

    free(table1);

}



void tri_fusion_bis(int tableau[],int deb,int fin){

    if (deb!=fin){

        int milieu=(fin+deb)/2;

        tri_fusion_bis(tableau,deb,milieu);

        tri_fusion_bis(tableau,milieu+1,fin);

        fusion(tableau,deb,milieu,fin);

    }

}



void tri_fusion(int *tableau,int longueur){

    if (longueur>0){

        tri_fusion_bis(tableau,0,longueur-1);

    }

}



void jeuxdetest(int *tableau){

}



void inversertableau(int *tableau, int n){

    int i,j=n-1;



    for (i = 0; i <= ((n-1)/2); i++){

            permute(&tableau[i], &tableau[j]);

            j--;

    }

}



int *inverseTab(int *tabval, int n)

{

      int i,j=0;

    int *t2;



    t2 = malloc(n*sizeof(int));



         for (i=(n-1);i >= 0;i--){



           t2[j] = tabval[i];



           j++;

      }



      return t2;

}



int main(){

    long double deb, fin, temps;

    int i = 0, choix, nbval;

    int *tabval;





    printf("* BASE DE LA COMPLEXITE, TP2 : *\n\n");



    printf("* MENU : *\n");

    printf("  - [1] : Tri par sélection\n");

    printf("  - [2] : Tri par insertion\n");

    printf("  - [3] : Tri à bulles\n");

    printf("  - [4] : Tri fusion\n");

    printf("  - [5] : Générer un tableau de nombre aléatoire\n\n");

    printf("Faite votre choix [0 pour quitter] : ");

    scanf("%i", &choix);

    switch(choix){

        case 0 : {

            _exit(0);

            break;

        }

        case 1 : {

            printf("\n\nSaisir le nombre de valeur à trier : ");

            scanf("%i", &nbval);

            tabval = (int *) malloc(nbval * sizeof(int));

            printf("\nSaisir les valeurs du tableau à trier : \n");

            for (i = 0; i < nbval; i++){

                scanf("%i", &tabval[i]);

            }

            printf("\n\n-> Fonction : Tri_Selection(tabvaleur)\n");

            deb=clock();

            tri_selection(tabval, nbval);

            fin=clock();

            affichertableau(tabval, nbval);

            temps=(1000* (fin-deb)/CLOCKS_PER_SEC);

            printf("\n  > Temps : %Lf ms\n\n\n", temps);

            break;

        }

        case 2 : {

            printf("\n\nSaisir le nombre de valeur à trier : ");

            scanf("%i", &nbval);

            tabval = (int *) malloc(nbval * sizeof(int));

            printf("\nSaisir les valeurs du tableau à trier : \n");

            for (i = 0; i < nbval; i++){

                scanf("%i", &tabval[i]);

            }

            printf("\n\n-> Fonction : Tri_Insertion(tabvaleur)\n");

            deb=clock();

            tri_insertion(tabval, nbval);

            fin=clock();

            affichertableau(tabval, nbval);

            temps=(1000* (fin-deb)/CLOCKS_PER_SEC);

            printf("\n  > Temps : %Lf ms\n\n\n", temps);

            break;

        }

        case 3 : {

            printf("\n\nSaisir le nombre de valeur à trier : ");

            scanf("%i", &nbval);

            tabval = (int *) malloc(nbval * sizeof(int));

            printf("\nSaisir les valeurs du tableau à trier : \n");

            for (i = 0; i < nbval; i++){

                scanf("%i", &tabval[i]);

            }

            printf("\n\n-> Fonction : Tri_A_Bulle(tabvaleur)\n");

            deb=clock();

            tri_bulle(tabval, nbval);

            fin=clock();

            affichertableau(tabval, nbval);

            temps=(1000* (fin-deb)/CLOCKS_PER_SEC);

            printf("\n  > Temps : %Lf ms\n\n\n", temps);

            break;

        }

        case 4 : {

            printf("\n\nSaisir le nombre de valeur à trier : ");

            scanf("%i", &nbval);

            tabval = (int *) malloc(nbval * sizeof(int));

            printf("\nSaisir les valeurs du tableau à trier : \n");

            for (i = 0; i < nbval; i++){

                scanf("%i", &tabval[i]);

            }

            printf("\n\n-> Fonction : Tri_Fusion(tabvaleur)\n");

            deb=clock();

            tri_fusion(tabval, nbval);

            fin=clock();

            affichertableau(tabval, nbval);

            temps=(1000* (fin-deb)/CLOCKS_PER_SEC);

            printf("\n  > Temps : %Lf ms\n\n\n", temps);

            break;

        }

        case 5 : {

            printf("\n\nSaisir le nombre de valeur à trier : ");

            scanf("%i", &nbval);

            tabval = (int *) malloc(nbval * sizeof(int));

            generertableaualeatoire(tabval, nbval);

            affichertableau(tabval, nbval);

            jeuxdetest(tabval);

            inversertableau(tabval, nbval);

            affichertableau(tabval, nbval);

            tabval = inverseTab(tabval, nbval);

            affichertableau(tabval, nbval);

            break;

        }

        default :{

            main();

        }

    }

    return 0;

}