ssort.c

不同的排序算法的源程序

/***********************************************************************/
/*  SORT(): Non-Recursive Shell's Sort function.                       */
/*  See the function declaration for calling information.              */
/* Function is by Bruce Feist; please contact me on CompuServe with    */
/*    a message on BPROGB, MACDEV, or EASYPLEX if you have any         */
/*    questions or problems.                                           */
/* You can also reach me at the Enlightened Board, at [phone],  */
/*   N/8/1                                                             */
/* Feel free to make use of this code in your own programs.            */
/***********************************************************************/
/* Shell's sort.  Not bad for intermediate sizes. */
/* Uses increment sequence h(n+1) = 3*h(n) + 1,   */
/* as suggested by Knuth. */

#include <alloc.h>
#include <mem.h>
#include <stddef.h>
#include <stdio.h>

#include "sort.h"

#define VERBOSE (0)

static char *base;
static double *dbase;
static int nelem, width;
static int (*compare) (void *, void *);
static int get_increment (int n_elements);
static char *temp_record;

int
ssort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
{
  register unsigned int increment;
  long offset;
  register unsigned int equiv_class;

  base = pbase;
  dbase = pbase; /* for debugging only */
  nelem = pnelem;
  width = pwidth;
  compare = pcompare;

  temp_record = malloc (width);
  if (temp_record == NULL)
	return S_NOMEM;

  for (increment = get_increment (nelem);
       increment > 0;
       increment /= 3)
  {
    for (equiv_class = increment;
	 equiv_class < nelem;
	 equiv_class++)
    {
      memcpy (temp_record, base + equiv_class * width, width);
      for (offset = equiv_class - increment;
	   offset >= 0 &&
#pragma warn -sig
	     (*compare) (temp_record, base + offset * width) < 0;
#pragma warn .sig
	   offset -= increment)
      {
#pragma warn -sig
	memcpy (base + (increment + offset) * width,
		base + offset * width,
#pragma warn .sig
		width);
	}  /* end for offset */

#pragma warn -sig
      memcpy (base + (offset + increment) * width, temp_record, width);
#pragma warn .sig
      } /* end for equiv_class */
    } /* end for increment */

  return S_OK;
  }  /* end ssort */

  int
  get_increment (int n_elements)
  {
    register int inc;

    for (inc = 1;
	 inc < n_elements;
	 inc = 3 * inc + 1)
      ;

    return inc > 17 ? inc/9 : 1;
    } /* end get_increment */