/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        T E S T   C R O I S S A N T   D ' U N   T R I   E N   ' N * L O G ( N ) '   E N   M O D E   V I R T U E L  :               */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*        Author of '$xtc/tri_NLogN.02$c' :                                                                                          */
/*                                                                                                                                   */
/*                    Jean-Francois COLONNA (LACTAMME, AAAAMMJJhhmmss).                                                              */
/*                                                                                                                                   */
/*************************************************************************************************************************************/

#include  <stdio.h>

extern    double    drand48();
#define   RANDOM                                                                                                                        \
                    (drand48()-0.5)

#define   FACTEUR                                                                                                                       \
                    100

#define   INDEX0                                                                                                                        \
                    0
#define   INDEXn                                                                                                                        \
                    10

#define   VRAI                                                                                                                          \
                    1
#define   FAUX                                                                                                                          \
                    0

#define   compcl(index1,index2)                                                                                                         \
                    (tableau[permutation[index1]]-tableau[permutation[index2]])

#define   echang(index1,index2)                                                                                                         \
                    {                                                                                                                   \
                    int       tempo=permutation[index1];                                                                                \
                    permutation[index1] = permutation[index2];                                                                          \
                    permutation[index2] = tempo;                                                                                        \
                    }

static    int       tableau[INDEXn-INDEX0+1];
static    int       permutation[INDEXn-INDEX0+1];

tri(debut,fin)
int       debut;
int       fin;
          {
          int       index=fin/2;

          while     (index>=debut)
                    {
                    reorg(index,fin);
                    index=index-1;
                    }

          index=fin;

          while     (index>debut)
                    {
                    echang(debut,index);
                                        /* Cette echange ne conserve malheureusement pas l'ordre des elements de meme "clef"...      */
                    index=index-1;
                    reorg(debut,index);
                    }

          return(VRAI);
          }

reorg(debut,fin)
          {
          int       j=debut;
          int       iter=VRAI;

          while     (iter==VRAI)
                    {
                    int       gauche=2*j;

                    if        (gauche>fin)
                              {
                              iter=FAUX;
                              }
                    else
                              {
                              int       indmax=gauche;
                              int       droite=gauche+1;

                              if        (droite>fin)
                                        {
                                        }
                              else
                                        {
                                        if        (compcl(gauche,droite)<0)
                                        /* Rappelons que le tri est croissant...                                                     */
                                                  {
                                                  indmax=droite;
                                                  }
                                        else
                                                  {
                                                  }
                                        }

                              if        (compcl(indmax,j)<=0)
                                        /* Rappelons que le tri est croissant...                                                     */
                                        {
                                        iter=FAUX;
                                        }
                              else
                                        {
                                        echang(j,indmax);
                                        /* Cette echange ne conserve malheureusement pas l'ordre des elements de meme "clef"...      */
                                        j=indmax;
                                        }
                              }
                    }
          return(VRAI);
          }

main()
          {
          int       n;

          for       (n=INDEX0 ; n<=INDEXn ; n++)
                    {
                    tableau[n] = (int)(FACTEUR*RANDOM);
                    permutation[n] = n;
                    printf("\n tableau[%02d]=%d",n,tableau[n]);
                    }
          printf("\n");

          tri(INDEX0,INDEXn);

          for       (n=INDEX0 ; n<=INDEXn ; n++)
                    {
                    printf("\n tableau[%02d-->%02d]=%d",permutation[n],n,tableau[permutation[n]]);
                    }
          }