/*Le tri tas est un tri "en place", c'est-à-dire que les éléments
sont insérés et triés dans un unique tableau. Après leur insertion
dans le tableau, les éléments sont tout d'abord rangés "en tas", le
tableau simulant ce tas. Un tas est un arbre binaire "parfait" : toutes les
rangées de l'arbre sont pleines sauf éventuellement la dernière ;
la dernière rangée est remplie de gauche à droite. Si on numérote les sommets
de cet arbre de gauche à droite, dans chaque rangée, et de haut en bas, la
racine ayant le numéro 1, on voit que les fils du sommet numéroté i sont
numérotés 2i et 2i+1. Il y a donc une bijection naturelle entre les noeuds
d'un tel arbre et les positions d'indice i, pour i variant entre 1 et n dans
le tableau. A chaque sommet de l'arbre on associe un des éléments à trier.
Pour que l'arbre binaire parfait soit un tas, il faut qu'en chaque sommet
l'élément qui s'y trouve soit plus grand que ceux situés en ses deux fils.
  Un algorithme possible de construction d'un tas est le suivant : on considère
que l'on introduit les uns après les autres les éléments dans le tas, dont la
structure est reconstituée après chaque insertion. Pour mettre à sa place
l'élément en cours d'insertion, on l'introduit à la première place disponible,
puis on le compare à son père : s'il est plus grand que son père, on l'échange
avec son celui-ci ; on recommence ces échanges jusqu'à ce que l'élément à insérer
soit plus petit que son père ou qu'il ait atteint la racine.
  Une fois le tas construit avec tous les éléments à trier, le maximum de
ceux-ci se trouve à la racine. On peut donc utiliser le tas pour trier les
éléments : on retire la racine, on restaure la structure de tas sur les éléments
restants et on recommence. Pour restaurer la structure de tas, on place le
dernier élément du tas à la racine (à la place de l'élément qu'on vient de
retirer pour construire la liste triée ; en fait, pour ne pas consommer de place
supplémentaire, on échange la racine du tas courant et le dernier élément du
tas courant, et on considère que le tas courant est maintenant l'ancien tas courant
privé de son dernier élément), puis on le fait "descendre" dans le tas en l'échangeant
avec le plus grand de ses fils, si le plus grand de ses fils est plus grand que lui.
  Quand on a fini, le tableau contient les éléments dans l'ordre croissant.*/

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

#define INFINI INT_MAX /*plus grand int, valeur contenue dans limits.h*/

void construire_tas(int *,int);
void ranger_tas(int *,int);
void echanger(int *,int,int);
void afficher(int *,int);

void main ()
{
  int nbr_donnees, * tableau;
  
  printf("Quel nombre de données voulez-vous trier  ?  ");
  scanf("%d",&nbr_donnees);
  tableau = (int *)malloc((nbr_donnees+1)*sizeof(int));
  construire_tas(tableau,nbr_donnees);
  ranger_tas(tableau,nbr_donnees);
  afficher(tableau,nbr_donnees);
  free(tableau);
}

void echanger(int *tableau, int ind1,int ind2)
{
  int tampon;
  
  tampon=tableau[ind1];
  tableau[ind1]=tableau[ind2];
  tableau[ind2]=tampon;
}

void construire_tas(int * tableau,int nbr_donnees)
{
  /* A COMPLETER*/
} 

void ranger_tas(int *tableau,int nbr_donnees)
{
  /* A COMPLETER*/
}

void afficher(int *tableau,int nbr_donnees)
{
  int i;
  printf("Voici vos données triées\n");
  for (i=0;i<nbr_donnees;i++)
    printf("%4d%c",tableau[i+1],(i%5==4 ? '\n' : ' '));
  /* (i%5==4 ? '\n' : ' ') est une expression conditionnelle.
     Si la condition i%5==4 est vraie, l'expression prend la valeur '\n'
     sinon elle prend la valeur ' '*/
}