/*
 *	File: lex_quicksort.c
 *
 *      (C) IWTS
 *          KU Nijmegen
 *          The Netherlands
 *
 *      Author: K. Behnke
 *
 *      History:
 *
 *      - 12 mar 1999, version 1.0
 *
 *      Description:
 *
 *	Sorts an array arr[1..n] into ascending numerical
 *	order using the Quicksort algorithm.
 *	
 *	n is input, arr is replaced on output by
 *	its sorted rearrangement
 *
 *	Copied from W.H. Press, B.P. Flannery, S.A. Teukolsky,
 *	W.T. Vetterling (1990). "Numerical Recipes in C", Cambridge
 *	University Press, pp. 251-252.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include "lex_qck.h"


void qcksrt (n, arr)
int	n;
double	arr[];

{
  double		a;
  long		fx = 0L;
  int 		i, iq, ir, j,
		jstack = 0,
		l = 1,
		istack[NSTACK+1];

  ir = n;

  for (;;) {
    if ((ir - l) < MM) {
      for (j = l + 1; j <= ir; j++) {
        a = arr[j];

        for (i = j - 1; arr[i] > a && i > 0; i--) {
          arr[i+1] = arr[i];
        }

        arr[i+1] = a;
      }

      if (jstack == 0) {
        return;
      }

      ir = istack[jstack--];
      l = istack[jstack--];
    }
    else{
      i = l;
      j = ir;
      fx = (fx * FA + FC) % FM;
      iq = l + ((ir - l + 1) * fx) / FM;
      a = arr[iq];
      arr[iq] = arr[l];

      for (;;) {
        while (j > 0 && a < arr[j]) {
          j--;
        }

        if (j <= i) {
          arr[i]=a;
          break;
        }

        arr[i++] = arr[j];

        while (a > arr[i] && i <= n) {
          i++;
        }

        if (j <= i) {
          arr[(i=j)] = a;
          break;
        }

        arr[j--] = arr[i];
      }

      if (ir-i >= i-l) {
        istack[++jstack] = i+1;
        istack[++jstack] = ir;
        ir = i - 1;
      }
      else {
        istack[++jstack] = l;
        istack[++jstack] = i - 1;
        l = i + 1;
      }

      if (jstack > NSTACK) {
        fprintf (stderr, "NSTACK too small in QCKSRT\n");
        exit (1);
      }
    }
  }
}


void qcksrt2 (n, arr_sf, arr_wi)
int n;
int arr_sf[];
int arr_wi[];

{
  long		fx = 0L;
  int 		a, aa, i, ii,
		iq, ir, j,
		jstack = 0,
		l = 1,
		istack[NSTACK+1];

  ir = n;

  for (;;) {
    if (ir-l < MM) {
      for (j = l + 1; j <= ir; j++) {
        a = arr_sf[j];
        aa = arr_wi[j];

        for (i = j - 1; arr_sf[i] > a && i > 0; i--) {
          arr_sf[i+1] = arr_sf[i];
          arr_wi[i+1] = arr_wi[i];
        }

        arr_sf[i+1] = a;
        arr_wi[i+1] = aa;
      }

      if (jstack == 0) {
        return;
      }

      ir = istack[jstack--];
      l = istack[jstack--];
    }
    else{
      i = l;
      j = ir;
      fx = (fx * FA + FC) % FM;
      iq = l + ((ir - l + 1) * fx) / FM;
      a = arr_sf[iq];
      aa = arr_wi[iq];
      arr_sf[iq] = arr_sf[l];
      arr_wi[iq] = arr_wi[l];

      for (;;) {
        while (j > 0 && a < arr_sf[j]) {
          j--;
        }

        if (j <= i) {
          arr_sf[i]=a;
          arr_wi[i] = aa;
          break;
        }

        ii = i;
        arr_sf[i++] = arr_sf[j];
        arr_wi[ii] = arr_wi[j];

        while (a > arr_sf[i] && i <= n) {
          i++;
        }

        if (j <= i) {
          arr_sf[(i=j)] = a;
          arr_wi[(i=j)] = aa;
          break;
        }

        ii = j;
        arr_sf[j--] = arr_sf[i];
        arr_wi[ii] = arr_wi[i];
      }

      if (ir-i >= i-l) {
        istack[++jstack] = i+1;
        istack[++jstack] = ir;
        ir = i - 1;
      }
      else {
        istack[++jstack] = l;
        istack[++jstack] = i - 1;
        l = i + 1;
      }

      if (jstack > NSTACK) {
        fprintf (stderr, "NSTACK too small in QCKSRT\n");
        exit (1);
      }
    }
  }
}
