/* Le tri rapide utilise une fonction que l'on appelle ici partition.
La fonction partition(tableau, gauche, droite) utilise un tableau, et 
deux indices de ce tableau, que nous notons gauche et droite. Elle 
particularise la donnée tableau[gauche] que nous appelons cle. Elle doit 
alors déplacer les données du tableau se situant entre gauche et droite 
de telle sorte que l'on trouve, de la gauche vers la droite, entre les 
indices gauche et droite :
- les données <= cle
- la cle
- les données > cle.
La fonction partition rend l'indice de la clé après le partitionnement.
Plusieurs façons de procéder sont possibles. A vous d'en construire une.
Un détail peut vous faciliter le travail ; nous l'avons programmé pour vous :
il peut être utile d'avoir mis à la droite du tableau à trier une donnée 
fictive plus grande que toutes les données du tableau : c'est ce qu'on 
appelle une "sentinelle".

Il vous faudra écrire aussi la fonction tri_rapide ;
cette fonction doit trier le tableau "tableau  en utilisant la fonction 
partition. Dans cet exercice, la fonction tri_rapide ne devra pas être 
récursive.*/

#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)
{  
  /* A COMPLETER*/
}

int partition(float * tableau, int gauche, int droite)
{
  float cle;
  int i,j;
  
  cle=tableau[gauche];
  i=gauche+1;
  j=droite;
  while (i<=j)
    {
      while (tableau[i]<=cle) i++;
      while (tableau[j]>cle) j--;
      if (i<j) echanger(tableau, i++, j--);
    }
  echanger(tableau, gauche, 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");
}