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

#ifndef element
#define element float
#endif
#define limit   15

/*----------------------------------------------------------------------*/
/* The following procedure sorts the subvector r[lo..up] by repeated    */
/* partitioning, using r[lo] as pivot. The left partition is sorted     */
/* recursively and the right part iteratively. Subvectors smaller than  */
/* limit are sorted later by insertion sort.                            */
/*----------------------------------------------------------------------*/
static void q_sort(r, lo, up)
  element r[];
  int lo, up;
{
  int i, j;
  element pivot;

  while (up >= (lo+limit))
    { i = lo; j = up;
      pivot = r[lo];
      while (i<j)                /* Partitioning loop */
	{ while (r[j] > pivot) j--;
	  r[i] = r[j];
	  while ((i<j) && (r[i]<=pivot)) i++;
	  r[j] = r[i];
	}
      r[i] = pivot;
      q_sort(r, lo, i-1);        /* Recursive call for left part */
      lo = i+1;                  /* Lower bound of the right part */
    }
}                                /* End of q_sort */

/*----------------------------------------------------------------------*/
/* Insertion sort for the whole vector. A sentinel technique is used;   */
/* a suitable sentinel element is found from r[0..limit].               */
/*----------------------------------------------------------------------*/
static void i_sort_after_q_sort(r, n)
  element r[];
  int n;
{
  int i, j;
  element sentinel, aux;

  sentinel = r[0];
  for (i=1; (i<=limit) && (i<n); i++)
    if (r[i]<sentinel)
      { 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;
    }
}                                /* End of i_sort */

/*----------------------------------------------------------------------*/
/* Gather up the sort procedure by using the above tools.               */
/*----------------------------------------------------------------------*/
void quicksort(r, n)
  element r[];
  int n;
{
  q_sort(r, 0, n-1);
  i_sort_after_q_sort(r, n);
}                                /* End of quicksort */