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

void measure(int action, int size);
int* randomTab(int size);
int getSize();
void menu(int size);
void printTab(int* t, int n);

void triSelection(int* t, int n);
void triInsertion(int* t, int n);
void triBulle(int* t, int n);
void triFusion(int* t, int debut, int fin);
void fusionner(int* t, int debut, int milieu, int fin);
void triRapide(int* t, int debut, int fin);
int partitionner(int* t, int debut, int fin);

int main()
{
    srand(time(NULL));
    int size = 50000;
    int action;
    do
    {
        menu(size);
        int res = 0;
        do {
            res = scanf("%d",&action);
            char ch;
            while ((ch = getchar()) != '\n' && ch != EOF); 
        } while (res<1);
        switch (action)
        {
               case 1: size = getSize(); break;
               case 2: 
               case 3: 
               case 4: 
               case 5: 
               case 6: measure(action, size); break;
               default: printf("Veuillez retaper 0...6\n");
        }
    } while (action>0);
    printf ("Merci et au revoir.\n");    
    return 0;
}        


void measure(int action, int size)
{
    clock_t debut, fin;
    int i;
    int* t = randomTab(size);
    // printTab(t,size);
    debut=clock();
    switch (action)
    {
               case 2: printf("Debut tri Selection...\n"); triSelection(t,size); break;
               case 3: printf("Debut tri Insertion...\n"); triInsertion(t,size); break;
               case 4: printf("Debut tri Bulle...\n"); triBulle(t,size); break;
               case 5: printf("Debut tri Fusion...\n"); triFusion(t,0,size-1); break;
               case 6: printf("Debut tri Rapide...\n"); triRapide(t,0,size-1); break;;
    }
    fin=clock();
    // printTab(t,size);
    float difference = (float)(fin-debut)/(float)CLOCKS_PER_SEC;
    printf("Duree : %f secondes\n", difference);
    free(t);
}

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

void triSelection(int* t, int n)
{    
     int i, j, posmin;
     for (i=0;i<n-1;i++)
     {
         posmin = i;
         for (j=i+1;j<n;j++)
                  if (t[j]<t[posmin]) posmin = j;
         if (posmin!=i)
         {
                       int tmp = t[posmin];
                       t[posmin] = t[i];
                       t[i] = tmp;
         }
     }
}

void triInsertion(int* t, int n)
{
     int i, j;
     for (i=1;i<n;i++)
     {
         j = i;
         while (j>0 && t[j]<t[j-1]) {
               int tmp = t[j];
               t[j] = t[j-1];
               t[j-1] = tmp;
               j--;
         }    
     }
}

void triBulle(int* t, int n)
{
     int i,desordre = 1;
     while (desordre)
     {
           desordre = 0;
           for (i=0;i<n-1;i++)
               if (t[i]>t[i+1]) {
                   int tmp = t[i];
                   t[i] = t[i+1];
                   t[i+1] = tmp;
                   desordre = 1;
               }
     }
}         

void triFusion(int* t, int debut, int fin)
{
    if (debut < fin) 
    {
              int mid = (debut + fin)/2;
              triFusion(t, debut, mid);
              triFusion(t, mid+1, fin);
              fusionner(t,debut,mid,fin);
    }
}         

void fusionner(int* t, int debut, int milieu, int fin)
{
     int* tmp = (int*)malloc((fin-debut+1)*sizeof(int));
     int i = 0;
     int i1 = debut;
     int i2 = milieu+1;
     while (i1<=milieu && i2<=fin) {
           if (t[i1]<t[i2])
           {
                           tmp[i] = t[i1];
                           i1++;
           } else
           {
                           tmp[i] = t[i2];
                           i2++;
                           }
           i++;
     }
     while (i1<=milieu) {
           tmp[i] = t[i1];
           i1++;
           i++;
     }
     while (i2<=fin) {
           tmp[i] = t[i2];
           i2++;
           i++;
     }
     for (i=0;i<(fin-debut+1);i++) t[i+debut] = tmp[i];
     free(tmp);
}
    
void triRapide(int* t, int debut, int fin)
{
    if (debut < fin) 
    {
              int indexPivot = partitionner(t,debut,fin);
              triRapide(t, debut, indexPivot-1);
              triRapide(t, indexPivot+1, fin);
    }
} 

int partitionner(int* t, int debut, int fin)
{
    int i = debut+1;
    int j = fin;
    int pivot = t[debut];
    while (i<j) {
          while (i<j && t[i]<=pivot) i++;
          while (i<j && t[j]>=pivot) j--;
          if (i<j) {
                   int tmp = t[i];
                   t[i] = t[j];
                   t[j] = tmp;
          }
    }
    if (t[i]>pivot) i--;
    t[debut] = t[i];
    t[i] = pivot;
    return i;
}
    
int* randomTab(int size)
{
     printf("Creation d'un tableau de %d cases...\n", size);
     int* t = (int*)malloc(size*sizeof(int));
     int i;
     for (i=0;i<size;i++) t[i] = rand()%10000;
     return t;
}

int getSize() {
    int res, n;
    do {
        printf("Nouvelle taille des tableaux? ");
        res = scanf("%d",&n);
        char ch;
        while ((ch = getchar()) != '\n' && ch != EOF); 
    } while (res<1);
    return n;
}

void menu(int size)
{
     printf("Choisir une action\n");
     printf("1 - Modifier la taille des tableaux a trier (valeur actuelle: %d)\n", size);
     printf("2 - Trier un tableau aleatoire par tri selection\n");
     printf("3 - Trier un tableau aleatoire par tri insertion\n");
     printf("4 - Trier un tableau aleatoire par tri bulle\n");
     printf("5 - Trier un tableau aleatoire par tri fusion\n");
     printf("6 - Trier un tableau aleatoire par tri rapide\n");
     printf("0 - Quitter\n");
}