/**************************************************************
*         Sorting an array with the Quicksort method          *
* ----------------------------------------------------------- *
* REFERENCE:                                                  *
*                                                             *
*   "NUMERICAL RECIPES by W.H. Press, B.P. Flannery,          *
*    S.A. Teukolsky and W.T. Vetterling, Cambridge            *
*    University Press, 1986".                                 *
*                                                             *
*                                 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 ARR of length N into ascending numerical *
* order using the Quicksort algorithm. N is input, ARR is *
* replaced on output by its sorted rearrangement.         *
**********************************************************/ 
void QCKSRT(int N, float *ARR) {

  const int M=7, NSTACK=50;
/* Here M is the size of subarrays sorted by straight insertion, 
   NSTACK is the required auxuliary storage. */

   int I, IQ, IR, ISTACK[NSTACK], J, JSTACK, L;
   float A;
   JSTACK=0;
   L=1; IR=N;
e10:if (IR-L < M) {
	  for (J=L+1; J<=IR; J++) {
	   A=ARR[J];
	   for (I=J-1; I>0; I--) {
	     if (ARR[I] <= A) goto e12;
		 ARR[I+1]=ARR[I];
       }
       I=0;
e12:   ARR[I+1]=A;
	  }
      if (JSTACK == 0) return;
	  IR=ISTACK[JSTACK];
	  L=ISTACK[JSTACK-1];
	  JSTACK=JSTACK-2;
	} 
    else {
      I=L; J=IR;
	  //Generate a random integer IQ between L and IR inclusive.
	  IQ=(int) floor(L+(IR-L)*rand()/32767);
	  A=ARR[IQ];
	  ARR[IQ]=ARR[L];
e20:  if (J > 0) {
e21:    if (A < ARR[J]) {
          J--;
		  goto e21;
        }
	  }
	  if (J <= I) {
	     ARR[I]=A;
		 goto e30;
	  }
	  ARR[I]=ARR[J];
	  I++;
e22:  if (I <= N) {
		if (A > ARR[I]) {
	      I++;
		  goto e22;
		}
	  }
	  if (J <= I) {
	    ARR[J]=A;
	    I=J;
	    goto e30;
	  }
	  ARR[J]=ARR[I]; 	  	    
	  J--;	 	 
      goto e20;
e30:  JSTACK += 2;
      if (JSTACK > NSTACK) printf(" NSTACK too small!\n");
	  if (IR-I >= I-L) {
	    ISTACK[JSTACK]=IR;
	    ISTACK[JSTACK-1]=I+1;
	    IR=I-1;
      }
	  else {
	    ISTACK[JSTACK]=I-1;
	    ISTACK[JSTACK-1]=L;
	    L=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
  QCKSRT(N,A);

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

  printf("\n");

}

// end of file tqcksrt.cpp