/*                      FICHIER CONTENANT DES FONCTIONS PERMETTANT DE      */
/*                         TRIER RAPIDEMENT UN TABLEAU D'ENTIERS           */
/*                                                                         */
/* EXEMPLE : tableau = (3 7 1 4 2)                                         */
/*           on prend le premier element comme pivot                       */
/*           Inf recoit les elements inferieurs au pivot : Inf = (1 2)     */
/*           Sup recoit les elements superieurs au pivot : Sup = (7 4)     */
/*           le tableau concatenation de Inf, 3 (le pivot) et Sup avec     */
/*           Inf et Sup triés de la même manière (appel recursif)          */
/*                                                                         */
/* Creation : MM 13/09/2000                                                */

#include<stdio.h>

/* Fonction d'AFFICHAGE d'un tableau d'entiers : affiche */
/* Parametres : un tableau d'entiers : int* ipTableau    */
/*              la taille du tableau : int iTaille       */
/* Creation :  MM 13/09/2000                             */
/* Derniere mise a jour : MM  13/09/2000                 */
void affiche(int *ipTableau, int iTaille)
{
  int iCompteur;

  /* Affichage du tableau */
  printf("(");
  if(iTaille == 0) printf(")\n");
  else 
    if(iTaille == 1) printf("%d)\n",*(ipTableau));
      else 
       for(iCompteur=0;iCompteur<iTaille;iCompteur++)
	{
	 if(iCompteur < iTaille -1) printf("%d ",*(ipTableau+iCompteur));
	 else printf("%d)\n",*(ipTableau+iCompteur));
        }
}

/* Fonction de TRI RAPIDE d'un tableau d'entier : tri_rapide            */
/* Description : un pivot est choisi dans le tableau (le 1er element)   */
/*               le tableau est découpé en deux sous-tableau Inf et Sup */
/*               contenant respectivement les entiers inférieurs et     */
/*               les entiers supérieurs au pivot.                       */
/*               le tableau renvoyé contient la concaténation de Inf    */
/*               trié (par appel récursif), du pivot et de Sup trié.    */
/*                                                                      */
/* Paramètre d'entrée : un tableau d'entiers : int *iPtableau           */
/*                      la taille de ce tableau : int iTaille           */
/* Retour : un tableau d'entiers (int *)                                */
/* Creation : MM 13/09/2000                                             */
/* Derniere mise a jour : 13/09/2000                                    */
int* tri_rapide(int * ipTableau, int iTaille)
{
  /* Pivot du tableau : 1er element */
  int iPivot;
  /* Tableau contenant les éléments < au pivot */
  int* ipInf;
  /* Nombre d'elements du tableau Inf */
  int iTailleInf=0;
  /* Tableau contenant les éléments > au pivot */
  int* ipSup;
  /* Nombre d'elements du tableau Sup */
  int iTailleSup=0;
  /* Compteur */
  int iCompteur;

  /* Si le tableau contient moins de 2 éléments, on ne fait rien */
  if (iTaille < 2) return ipTableau;
  else
    {
      iPivot=*ipTableau;

      /* Ecriture des tableaux Inf et Sup                 */
      /* Chacun contiendra au maximum iTaille elements -1 */
      ipInf=(int*)malloc(sizeof(int)*(iTaille-1));
      ipSup=(int*)malloc(sizeof(int)*(iTaille-1));
      for(iCompteur=1;iCompteur<iTaille;iCompteur++)
	{
	  if(*(ipTableau+iCompteur)> iPivot) 
	    {
	      *(ipSup+iTailleSup)=*(ipTableau+iCompteur);
	      iTailleSup++;
	      //printf("Sup[%d]=%d\n",iTailleSup,*(ipTableau+iCompteur));
	    }
	  else
	    {
	      *(ipInf+iTailleInf)=*(ipTableau+iCompteur);
	      iTailleInf++;
	      //printf("Inf[%d]=%d\n",iTailleSup,*(ipTableau+iCompteur));
	    }
	} /* Fin du for */

      /* Reecriture du tableau à partir de Inf et Sup triés et du pivot */
      ipInf=tri_rapide(ipInf,iTailleInf);
      ipSup=tri_rapide(ipSup,iTailleSup);
      
      iTaille=0;
      /* Insertion des elements de Inf dans le tableau final */
      for(iCompteur=0;iCompteur<iTailleInf;iCompteur++)
	{
	  *(ipTableau+iCompteur)=*(ipInf+iCompteur);
	  iTaille++;
	}
      
      /* Insertion du pivot dans le tableau final */
      *(ipTableau+iCompteur)=iPivot;
      iTaille++;
     
      /* Insertion des elements de Sup dans le tableau final */
      for(iCompteur=0;iCompteur<iTailleSup;iCompteur++)
	{ 
	  *(ipTableau+iTaille)=*(ipSup+iCompteur);
	  iTaille++;
	}

      free(ipInf);
      free(ipSup);

      return ipTableau;
    }
}


/* PROGRAMME PRINCIPAL avec passage en paramètre d'un fichier           */
/* contenant en premier la taille d'un tableau puis les entiers du      */
/* tableaux séparés par des espaces                                     */
/* PAR EXEMPLE si le fichier contient la ligne : 9 10 5 12 2 9 1 3 4 7  */
/* Le resultat sera :                                                   */
/*                 > a.out
                   > Le tableau avant le tri est : (10 5 12 2 9 1 3 4 7)
                   > Le tableau après le tri est : (1 2 3 4 5 7 9 10 12) */
int main(int argc, char* argv[])
{
  /* Fichier contenant le tableau */
  FILE *FTableau;
  /* Taille du tableau */
  int iTaille;
  /* Tableau d'entiers */
  int *ipTableau;
  /* Compteur */
  int iCompteur;

  if((FTableau=fopen("tableau.txt","r"))==NULL)
    {
      printf("Erreur Ouverture du fichier\n");
    }
  else
    { /* Lecture de la taille du tableau */
      fscanf(FTableau,"%d",&iTaille);
      

      /* Allocation mémoire du tableau d'entiers */
      ipTableau=(int*)malloc(iTaille*sizeof(int));

      /* Ecriture du tableau à partir des données du fichier */
      for(iCompteur=0;iCompteur<iTaille;iCompteur++)
	fscanf(FTableau,"%d",(ipTableau+iCompteur));
	  
      printf("Le tableau avant le tri est : ");
      affiche(ipTableau,iTaille);

      ipTableau=tri_rapide(ipTableau,iTaille);

      printf("Le tableau après le tri est : ");
      affiche(ipTableau,iTaille);
      
      free(ipTableau);
      fclose(FTableau);
    }
}