/*----------------------------------------------------------------------*/
/*                         LINEAR PROBING SORT                          */
/* Adapted by J. Teuhola <teuhola@cs.utu.fi> from G. H. Gonnet &        */
/* R. Baeza-Yates: Handbook of Algorithms and Data Structures,          */
/* 2nd Edition, Addison-Wesley Publishing Company, 1991.                */
/*----------------------------------------------------------------------*/

#define element float

#ifndef PAIR
#define PAIR
typedef struct { element min, max; } pair;
#endif

#ifndef MINMAX
#define MINMAX
/*----------------------------------------------------------------------*/
/* Determine the minimum & maximum of r[0..n-1]. A special technique    */
/* with 1.5 comparisons per element is applied. The result is returned  */
/* as the minimum & maximum -pair.                                      */
/*----------------------------------------------------------------------*/
static pair minmax(r, n) 
  element r[];
  int n;
{
  int i;
  element x, y, min, max;
  pair p;

  min = r[n-1]; max = min;       /* Initial */
  for (i=0; i<n-1; i+=2)
    { x = r[i]; y = r[i+1];
      if (x<y)                   /* Inspect pairwise */
        { if (x<min) min = x;
          if (y>max) max = y; }
      else
        { if (x>max) max = x;
          if (y<min) min = y; }
    }
  p.min = min; p.max = max;
  return p;
}                                /* End of minmax */
#endif

/*----------------------------------------------------------------------*/
/* Sort the array r[0..n-1] by using w[0..m-1] as the distribution area */
/* where m = 1.4*n, and w[m..upper] as the overflow area; upper > 1.4n. */
/* The minimum key value should be larger than Lowvalue+1.              */
/*----------------------------------------------------------------------*/
void linear_probing_sort(r, w, n, upper)
     element r[], w[]; int n, upper;
{ int i, j, m;
  float x, aux, factor, low;
  pair p;

  m = 1.4 * n;                   /* The magic enlargement ratio */
  p = minmax(r, n);
  low = p.min-1.0;
  if (p.max > p.min)
    { factor = (float) m / (p.max-p.min);
      for (j=0; j<upper; j++) w[j] = low;
      for (j=0; j<n; j++)
        { x = r[j];
          for (i = factor*(x-p.min); w[i] > low; i++)  /* Probe */
	    { if (x<w[i])
	        { aux = w[i]; w[i] = x; x = aux; }
	      if (i > upper) goto error;
	    }
          w[i] = x;
        }
      i = 0;
      for (j=0; j<upper; j++)
        if (w[j] > low) r[i++] = w[j];
      return;
error: printf("*** Out of space ***\n");
    }
}                                /* End of linear_probing_sort */