/*
 * quicksort.c -- general purpose quick sort routine
 * (C)Copyright 1999 by Hiroshi Takekawa
 * This file is not part of any package.
 *
 * Last Modified: Sat Dec 11 02:11:06 1999.
 * $Id: quicksort.c,v 1.2 1999/12/23 15:16:46 sian Exp $
 *
 * Enfle is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Enfle is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <unistd.h>
#include "quicksort.h"

/* quick sortの仕上げのinsert sort */
static void
inssort(char **data, int n, int comp(void *, void *))
{
  int i, j;
  char *x;

  for (i = 1; i < n; i++) {
    x = data[i];
    for (j = i - 1; j >= 0 && comp(data[j], x) > 0; j--)
      data[j + 1] = data[j];
    data[j + 1] = x;
  }
}

/* 再帰なしquick sort */
void
quicksort(char **data, int n, int comp(void *, void *))
{
  int i, j, l = 0, r = n - 1, p = 0;
  char *t, *x;
  /* 端を覚えておくstack */
  int lstack[STACKSIZE], rstack[STACKSIZE];

  for (;;) {
    /* 閾値より小さくなったらそれより小さくしない */
    if (r - l <= THRESHOLD) {
      /* stackが空になったら終了 */
      if (p == 0)
	break;
      /* stackから値を取りだす */
      p--;
      l = lstack[p];
      r = rstack[p];
    }
    /* 基準となる値を選ぶ */
    x = data[(l + r) / 2];
    i = l;
    j = r;
    /* 基準によって左右にわける */
    for (;;) {
      while (comp(data[i], x) < 0)
	i++;
      while (comp(x, data[j]) < 0)
	j--;
      if (i >= j)
	break;
      t = data[i];
      data[i++] = data[j];
      data[j--] = t;
    }
    /* (実質上の)再帰 */
    if (i - l > r - j) {
      if (i - l > THRESHOLD) {
	lstack[p] = l;
	rstack[p] = i - 1;
	p++;
      }
      l = j + 1;
    } else {
      if (r - j > THRESHOLD) {
	lstack[p] = j + 1;
	rstack[p] = r;
	p++;
      }
      r = i - 1;
    }
  }

  /* しあげのinsert sortを呼ぶ */
  inssort(data, n, comp);
}