/**************************************************************
*          Sorting an array with the Heapsort method          *
* ----------------------------------------------------------- *
* REFERENCE:                                                  *
*                                                             *
*   "NUMERICAL RECIPES By W.H. Press, B.P. Flannery,          *
*    S.A. Teukolsky and W.T. Vetterling, Cambridge            *
*    University Press, 1986" [BIBLI 08].                      *
*                                                             *
*                                 C++ version by J-P Moreau   *
*                                     (www.jpmoreau.fr)       *
* ----------------------------------------------------------- *
* SAMPLE RUN:                                                 *
*                                                             *
* Table to be sorted:                                         *
*                                                             *
*     1   564   193   809   585   480   350   896   823   747 *
*   174   859   711   514   304    15    91   364   147   166 *
*   989   446   119     5     9   378   532   571   602   607 *
*   166   663   451   352    57   608   783   803   520   302 *
*   876   727   956   926   539   142   462   235   862   210 *
*   780   844   997  1000   611   392   266   297   840    24 *
*   376    93   677    56     9   919   276   273   588   691 *
*   838   726   485   205   744   468   458   949   744   108 *
*                                                             *   
* Sorted table (Heapsort method):                             *
*                                                             *
*     1     5     9     9    15    24    56    57    91    93 *
*   108   119   142   147   166   166   174   193   205   210 *
*   235   266   273   276   297   302   304   350   352   364 *
*   376   378   392   446   451   458   462   468   480   485 *
*   514   520   532   539   564   571   585   588   602   607 *
*   608   611   663   677   691   711   726   727   744   744 *
*   747   780   783   803   809   823   838   840   844   859 *
*   862   876   896   919   926   949   956   989   997  1000 *
*                                                             *
**************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define   SIZE   100                   //maximum size of table


float   A[SIZE];                       //table to be sorted
float   MAX_VALUE;                     //maximum value of table
float   temp;                          //auxiliary variable 
int     i,N;


/****************************************************
*  Sorts an array RA of length n in ascending order *
*                by the Heapsort method             *
* ------------------------------------------------- *
* INPUTS:                                           *
*	    n	  size of table RA                  *
*	    RA	  table to be sorted                *
* OUTPUT:                                           *
*	    RA	  table sorted in ascending order   *
*                                                   *
* NOTE: The Heapsort method is a N Log2 N routine,  *
*       and can be used for very large arrays.      *
****************************************************/         
void HPSORT(int n, float *RA)  {
// Labels: e10, e20
  int i,ir,j,l;
  float rra;

  l=(n/2)+1;
  ir=n;
  //The index L will be decremented from its initial value during the
  //"hiring" (heap creation) phase. Once it reaches 1, the index IR 
  //will be decremented from its initial value down to 1 during the
  //"retirement-and-promotion" (heap selection) phase.
e10: 
  if (l > 1) {
    l--;
    rra=RA[l];
  }
  else {
    rra=RA[ir];
    RA[ir]=RA[1];
    ir--;
    if (ir==1) {
      RA[1]=rra;
      return;
    }
  }
  i=l;
  j=l+l;
e20: 
  if (j <= ir) {
    if (j < ir)  
      if (RA[j] < RA[j+1]) j++;
    if (rra < RA[j]) {
      RA[i]=RA[j];
      i=j; j=j+j;
    }
    else
      j=ir+1;
    goto e20;
  }
  RA[i]=rra;
  goto e10;

} //HPSORT()


//write table of size N to standard output
void TWRIT(int N, float *ARR)  {
  int i; float tmp;
  printf("\n");;
  for (i=1; i<N+1; i++) {
    tmp=ARR[i];
    printf("%6.0f",tmp);
    if ((i % 10)==0) printf("\n");
  }
}


void main()  {

  N=80;     //initialize size of table
  MAX_VALUE = 1000.0;

  //generate random table of numbers (between 0 and MAX_VALUE)
  for (i=1; i<N+1; i++)  {
    temp = (float) rand();
    A[i] = MAX_VALUE*(temp/RAND_MAX);
  }

  printf("\n Table to be sorted:\n");
  TWRIT(N,A);
 
  //call sorting subroutine
  HPSORT(N,A);

  printf("\n Sorted table (Heapsort method):\n");
  TWRIT(N,A);

  printf("\n");

}

// end of file sort3.cpp