/*----------------------------------------------------------------------*/
/*               ADAPTIVE IN-PLACE LINEAR PROBING SORT                  */
/* Copyright (C) 1996 S. Carlsson   <Svante.Carlsson@sm.luth.se>        */
/*                    J. Katajainen <jyrki@di.ku.dk>                     */
/*                    J. Teuhola    <teuhola@cs.utu.fi>                 */
/* Published in DIKU Report 96/31, Department of Computer Science,      */
/* University of Copenhagen, Denmark.                                   */
/*                                                                      */
/* This program is free software; you can redistribute it and/or modify */
/* it under the terms of the GNU General Public License; version 2 of   */
/* the License or any later version. There is no warranty for the       */
/* program. See the GNU General Public License for more details.        */
/*----------------------------------------------------------------------*/

#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.                                      */
/*----------------------------------------------------------------------*/
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

/*----------------------------------------------------------------------*/
/* Determine the minimum of r[l..n-1].                                  */
/*----------------------------------------------------------------------*/
element minimum(r, l, n) 
  element r[];
  int l, n;
{
  int i;
  element min;

  min = r[l];
  for (i=l+1; i<n; i++)
    if (r[i]<min) min = r[i];
  return min;
}

#ifndef RIGHT_TO_LEFT_PARTITION
#define RIGHT_TO_LEFT_PARTITION
/*----------------------------------------------------------------------*/
/* Partition r[low..n-1] so that elements > pivot get left to the rest. */
/* The right-to-left wheel-technique is used, because there should be   */
/* fewer elements <= pivot. The hole technique is applied to minimize   */
/* the moves. The border is returned.                                   */
/*----------------------------------------------------------------------*/
int right_to_left_partition(pivot, r, low, n)
  element pivot, r[];
  int low, n;
{
  int i, j;
  element x;

  i = n-1;                       /* Start with empty wheel */
  x = r[i];                      /* Dig the hole */
  for (j=i-1; j>=low; j--)
    if (r[j]<=pivot)             /* Turn wheel? */
      { r[i--] = r[j]; r[j] = r[i]; }
  r[i] = x;                      /* Fill the hole */
  if (x<=pivot) return i;
  else return (i+1);
}                                /* End of left_to_right_partition */
#endif

#ifndef DISTRIBUTE
#define DISTRIBUTE
/*----------------------------------------------------------------------*/
/* Distribute elements r[mid..n-1] to r[low..mid-1] by linear probing.  */
/* Locations r[mid..] may have to be used as overflow area.             */
/*----------------------------------------------------------------------*/
void distribute(min, pivot, r, low, mid, n)
  element min, pivot, r[];
  int low, mid, n;
{
  int i, addr;
  float factor;
  element x, y;

/* Calculate the interpolation coefficient: */
  factor = (float)(mid-low)/(pivot-min);
  for (i=mid; i<n; i++)
    { x = r[i];
      for (addr=low+factor*(x-min); r[addr]<pivot; addr++)
        if (x<r[addr])           /* Linear probe */
          { y = r[addr];
            r[addr] = x;
            x = y; }
      r[i] = r[addr];
      r[addr] = x;
    }
}                                /* End of distribute */
#endif

#ifndef LEFT_TO_RIGHT_PARTITION
#define LEFT_TO_RIGHT_PARTITION
/*----------------------------------------------------------------------*/
/* Partition r[low..n-1] so that elements <= pivot are moved stably to  */
/* r[low..mid-1]. Again we apply the wheel and hole techniques.         */
/*----------------------------------------------------------------------*/
void left_to_right_partition(pivot, r, low, mid)
  element pivot, r[];
  int low, mid;
{
  int i, j;
  element x;

/* Skip the small elements at front */
  for (i=low; r[i]<=pivot; i++);
  x = r[i];                      /* Dig the hole */
  for (j=i+1; i<mid; j++)
    if (r[j]<=pivot)             /* Turn the wheel? */
      { r[i++] = r[j]; r[j] = r[i]; }
  r[mid] = x;                    /* Fill the hole */
}                                /* End of left_to_right_partition */
#endif

/*----------------------------------------------------------------------*/
/* Finally: sort the array r[0..n-1] by using the above tools.          */
/*----------------------------------------------------------------------*/
void adaptive_in_place_linear_probing_sort(r, n)
  element r[];
  int n;
{
  int i, j, l, m;
  element pivot, prev_pivot;
  pair p;

  p = minmax(r, n);
  l = 0;
  while ((l < n-1) && (p.min < p.max))
    { 
      pivot = p.min + 0.4 * (p.max - p.min);   /* The magic formula */
      prev_pivot = pivot + 1.0;  /* Pseudo value for loop condition */
      m = right_to_left_partition(pivot, r, l, n);
      while ((pivot < prev_pivot) &&   /* Prevent endless loop */
             (0.8*(m-l)<(n-m-1))) /* Non-uniform distribution? */
	{ 
          /* Reduce the size of the smaller element set */
          prev_pivot = pivot;
		  pivot = (p.min+pivot)/2;
		  m = right_to_left_partition(pivot, r, m, n);
	}
      if (m==n)                 /* No values <= pivot */
        p.min = minimum(r, l, n);  /* Find actual minimum */
      else
        { distribute(p.min, pivot, r, l, m, n);
          m = l + (n - m);
          left_to_right_partition(pivot, r, l, m);
          l = m;
          p.min = pivot;
	}
    }
}                                /* End of adaptive_in_place_..._sort */