/*----------------------------------------------------------------------*/
/*                  BUCKET SORT WITH COUNT ARRAY                        */
/* 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], where the     */
/* method is called INTERPOLATION SORT.                                 */
/*----------------------------------------------------------------------*/

#ifndef element
#define element float
#endif

#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

/*----------------------------------------------------------------------*/
/* The elements r[0..n-1] are allocated to buckets. The addresses are   */
/* stored into addr[0..n-1] for speed, and element counts in buckets in */
/* count[0..nbuckets-1]. The actual allocation is done to aux[0..n-1]   */
/* after determining the bucket sizes.                                  */
/*----------------------------------------------------------------------*/
static void b_sort(r, aux, addr, count, n, nbuckets, mini, maxi)
  element r[], aux[];
  int addr[], count[];
  int n, nbuckets;
  element mini, maxi;
{
  int i, j, k, cum;
  float factor;
  element x;

/* The multiplication factor for the interpolation formula: */
  factor = (float) (nbuckets-1) / (maxi-mini);
  for (i=0; i<nbuckets; i++) count[i] = 0;
  for (i=0; i<n; i++)
    { 
      addr[i] = (float) (r[i] - mini) * factor;
      count[addr[i]]++;
    }
  cum = 0;
  for (i=0; i<nbuckets; i++)
    { cum += count[i];
      count[i] = cum;
    }
  for (i=0; i<n; i++)
    aux[--count[addr[i]]] = r[i];
  for (i=0; i<n; i++) r[i] = aux[i];
}

/*----------------------------------------------------------------------*/
/* Insertion sort will be used to finalize the sort within buckets.     */
/* The whole array is sorted in one phase. A special version is applied,*/
/* with the minimum value as the sentinel at front, to speed-up looping.*/
/*----------------------------------------------------------------------*/
static void i_sort_after_b_sort(r, n, mini)
  element r[]; 
  int n;
  element mini;
{
  int i, j;
  element sentinel, aux;

  for (i=0; r[i]!=mini; i++);
  sentinel = r[i]; r[i] = r[0]; r[0] = sentinel;
  for (i=2; i<n; i++)
    {
      aux = r[i];
      for (j=i-1; r[j] > aux; j--) r[j+1] = r[j];
      r[j+1] = aux;
    }
}

/*----------------------------------------------------------------------*/
/* The actual sort routine just collects the phases.                    */
/* The array parameters r, aux and addr should all have space           */
/* allocation of 0..n-1, whereas the array 'count' needs only 0..n/10.  */
/*----------------------------------------------------------------------*/
void bucketsort(r, aux, addr, count, n)
     element r[], aux[];
     int addr[], count[], n;
{
  pair p;
  int nbuckets;

  p = minmax(r, n);
  if (p.min < p.max)
    {
      nbuckets = n/10;
      if (nbuckets == 0) nbuckets = 1;
      b_sort(r, aux, addr, count, n, nbuckets, p.min, p.max);
      i_sort_after_b_sort(r, n, p.min);
    }
}                                /* End of bucketsort */