/**************************************************
* Sorting an array with straight insertion 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              *
*                                                 *
* Sorted table (straight insertion):              *
*                                                 *
*      1      5      9     15     91              *
*    119    147    166    174    193              *
*    304    350    364    446    480              *
*    514    564    585    711    747              *
*    809    823    859    896    989              *
*                                                 *
**************************************************/
#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 straight insertion.                            *
* ------------------------------------------------- *
* INPUTS:                                           *
*	   N	  size of table ARR                 *
*      	   ARR	  table to be sorted                *
* OUTPUT:                                           *
*	   ARR    table sorted in ascending order   *
*                                                   *
* NOTE: Straight insertion is a Nē routine and      *
*       should only be used for relatively small    *
*       arrays (N<100).                             *
****************************************************/
void PIKSRT(int N, float *ARR)  {
//Label: e10
  int i,j; float a;
  for (j=2; j<N+1; j++) {
    a=ARR[j];
    for (i=j-1; i>0; i--) {
      if (ARR[i]<=a) goto e10;
      ARR[i+1]=ARR[i];
    }
    i=0;
e10: ARR[i+1]=a;
  }
}

//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 % 5)==0) printf("\n");
  }
}


void main()  {

  N=25;     //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
  PIKSRT(N,A);

  printf("\n Sorted table (straight insertion):\n");
  TWRIT(N,A);

  printf("\n");

}

// end of file sort1.cpp