/**************************************************************
*           Sorting an array with the Shell 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 (Shell 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 ARR of length N in ascending order *
*            by the Shell-Mezgar method             *
* ------------------------------------------------- *
* INPUTS:                                           *
*	   N	  size of table ARR                 *
*          ARR	  table to be sorted                *
* OUTPUT:                                           *
*	   ARR   table sorted in ascending order    *
*                                                   *
* NOTE: The Shell method is a N^3/2 routine and can *
*       be used for relatively large arrays.        *
****************************************************/
void SHELL(int n, float *ARR)  {
// Label: e10

#define   ALN2I  1.0/0.69314718
#define   TINY   1e-5

  float LOGNB2, t;
  int   i,j,k,l,m,nn;

  LOGNB2=(float) floor(log(N)*ALN2I+TINY);
  m=n;
  for (nn=1; nn<=floor(LOGNB2); nn++) {
    m=m / 2; k=n-m;
    for (j=1; j<k+1; j++) {
      i=j;
e10:  l=i+m;
      if (ARR[l] < ARR[i]) {
        t=ARR[i];
	ARR[i]=ARR[l];
        ARR[l]=t;
	i=i-m;
	if (i >= 1) goto e10;
      }
    }
  }
}


//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
  SHELL(N,A);

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

  printf("\n");

}

// end of file sort2.cpp