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

void lire(float *, int);
void tri_rapide(float *, int);
int partition(float *, int, int);
void echanger(float *, int, int);
void afficher(float *, int);

void main()
{
  int nb_donnees;
  float * tableau;
  
  printf("Combien voulez-vous trier de données ?  ");
  scanf("%d",&nb_donnees);
  if (nb_donnees==0) exit(0);
  tableau=(float *)malloc(sizeof(float)*(nb_donnees+1));
  /*un "de plus" pour la sentinelle*/
  lire(tableau, nb_donnees);
  tableau[nb_donnees]=FLT_MAX;
  tri_rapide(tableau,nb_donnees);
  afficher(tableau,nb_donnees);
  free(tableau);  
}

void lire(float *tableau, int nb_donnees)
{
  int i;
  
  printf("\nEntrez les %d données réelles à trier\n",nb_donnees);
  for (i=0;i<nb_donnees;i++) scanf("%f",tableau++);
}

void tri_rapide(float *tableau, int nb_donnees)
{
  int pivot,gauche,droite;
  int pile[50];
  int curseur=2;  
  /*cette taille du tableau pile permet de trier... un grand nombre de données*/
  
  pile[0]=0;
  pile[1]=nb_donnees-1;
  while (curseur>0)
    {
      droite=pile[--curseur];
      gauche=pile[--curseur];
      while (droite>gauche)
	{
	  pivot=partition(tableau, gauche, droite);
	  if ((droite-pivot)>(pivot-gauche))
	    /*partition a délimité deux sous-tableaux ; le plus petit des deux
	      va être traité tout de suite ; on empile les bornes du second
	      tableau de façon à le traiter plus tard*/
	    {
	      pile[curseur++]=pivot+1;
	      pile[curseur++]=droite;
	      droite=pivot-1;
	    }
	  else
	    {
	      pile[curseur++]=gauche;
	      pile[curseur++]=pivot-1;
	      gauche=pivot+1;
	    }
	}
    }
}

int partition(float * tableau, int g, int d)
{
  float cle;
  int i,j;
  
  cle=tableau[g];
  i=g+1;
  j=d;
  while (i<=j)
    {
      while (tableau[i]<=cle) i++;
      while (tableau[j]>cle) j--;
      if (i<j) echanger(tableau, i++, j--);
    }
  echanger(tableau, g, j);
  return j;
}

void echanger(float * tableau, int i, int j)
{
  float tampon;
  
  tampon=tableau[i];
  tableau[i]=tableau[j];
  tableau[j]=tampon;
}

void afficher(float * tableau,int nb_donnees)
{
  int i;
  
  printf("\nVoici le tableau trié\n");
  for (i=0;i<nb_donnees;i++) printf("%6.2f ",tableau[i]);
  printf("\n");
}