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

float measure(int action, int size);
int* randomTab(int size);
int getSize();
void menu(int size);
void printTab(int* t, int n);
void statistics();
char* name(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;
               case 7: statistics(); break;
               default: printf("Veuillez retaper 0...6\n");
        }
    } while (action>0);
    printf ("Merci et au revoir.\n");    
    return 0;
}        

char* name(int n) {
    switch (n)
    {
               case 1: return ";";
               case 2: return "Selection;";
               case 3: return "Insertion;";
               case 4: return "Bulle;";
               case 5: return "Fusion;";
               case 6: return "Rapide;";
               default: return "Unknown;";
    }
}
      
void statistics()
{
     // ouvrir d'un fichier en écriture 
     FILE *fic = fopen("stat.txt", "w");  
     if (fic == NULL) { 
        printf("Impossible d'ouvrir le fichier!\n"); 
        return; 
     }
     char str[100];
     int tabsize, tri;
     for (tri=1;tri<=6; tri++) // 1 n'est pas un tri
     {
         fputs(name(tri), fic); 
         for (tabsize=20000;tabsize<=100000; tabsize+=20000)
         {
             if (tri==1)
                sprintf(str,"%d;",tabsize);
             else
                sprintf(str,"%f;",measure(tri,tabsize));
             fputs(str, fic); 
         }
         fputs("\n", fic); 
     }
     // fermeture du fichier 
     if (fclose(fic) == EOF) { 
        printf("Problème de fermeture du fichier!\n"); 
        return; 
     }
}

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

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)
{
     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 de tableau? ");
        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("7 - Generer des statistiques dans stat.txt\n");
     printf("0 - Quitter\n");
}