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

void echange(int i, int j, int tab[], int n)
//echange les elements i et j du tableau tab de longueur n
{
 int x = tab[i];
 tab[i] = tab[j];
 tab[j] = x;
 return;
}

void descendre (int tab[], int n)
/* descend le premier element de tab 
jusqu'a ce qu'il soit plus grand que ses fils */
{
 int i = 0;
 while (1) {
//  printf("i = %d\n",i);
  if (2*i+1 < n && tab[2*i+1] > tab[i] && (2*i+2 == n || tab[2*i+1] > tab[2*i+2]))
  {
   echange(i,2*i+1,tab,n);
   i=2*i+1;
  }
  else if (2*i+2 < n && tab[2*i+2] > tab[i])
  {
   echange(i,2*i+2,tab,n);
   i=2*i+2;
  }
  else 
  {
   return;
  }
 }
}

void remonter (int tab[], int n)
// remonte le dernier element de tab pour qu'il soit plus petit que son pere
{
 int i=n-1;
 while (1)
 {
  if (i>0 && tab[i]>tab[(i-1)/2])
  {
   echange(i,(i-1)/2,tab,n);
   i=(i-1)/2;
  }
  else
  {
   return;
  }
 }
}

void construire_tas (int tab[], int n)
{
 int k;
 for (k=1; k<=n;k++) {
  remonter(tab,k); 
 }
 return;
}

void tri_par_tas (int tab[], int n)
{
 construire_tas(tab,n);
// printtab(tab,n);
 int k;
 for (k=n-1; k>0; k--) {
  echange(0,k,tab,n);
  descendre(tab,k);
//  printtab(tab,n);
 }
 return;
}

void printtab (int tab[], int n)
{
  int i;
  for (i=0;i<n;i++) {
   printf("%d ",tab[i]);
  }
  printf("\n");
}

int bien_trie (int tab[], int n) /* renvoie 1 si le tableau est bien trie,
0 sinon */
{
  int i;
  for (i=1; i<n; i++) {
    if (tab[i] < tab[i-1]) {
      return 0;
    }
  }
  return 1;
}

int main()
{
  srand(time(NULL));
  #define longueur_tableau 100

  int tab[longueur_tableau];

  int i;
  for (i=0;i<longueur_tableau;i++) {
   tab[i] = rand() % 100;
  } // initialisation du tableau

  printtab(tab,longueur_tableau); // affichage du tableau initial
  printf("----\n");

  tri_par_tas(tab,longueur_tableau); // tri du tableau

  printtab(tab,longueur_tableau); // affichage du tableau trie
  if (bien_trie(tab,longueur_tableau)) {
    printf("Le tableau est bien trie\n");
  }
  else {
    printf("Attention, le tableau n'est pas bien trie !\n");
  }
  return 0;
}