isort.c

不同的排序算法的源程序

/***********************************************************************/
/*  isort(): Non-Recursive Insertion 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.            */
/***********************************************************************/

/* Insertion sort.  Boring, but effective on small arrays. */
/* Do NOT use this on a randomly-ordered, large array.     */

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

#include "sort.h"

static char *base;
static int nelem, width;
static int (*compare) (void *, void *);

int
isort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
{
  char *temp_record, *left_ptr, *right_ptr, *last_ptr;

  base = pbase;
  nelem = pnelem;
  width = pwidth;
  compare = pcompare;

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

  last_ptr = base + (nelem - 1) * width;

  /* This loop assumes that the first i-1 entries are in order. */
  /* It then positions the ith entry in their midst, so that the */
  /* first i entries are in order. */

  for (right_ptr = base + width;
       right_ptr <= last_ptr;
       right_ptr += width)
  {
#if VERBOSE
    printf ("Pass # %d\n", (right_ptr - base) / width);
#endif
	memcpy (temp_record, right_ptr, width);

	/* This loop finds out where the new entry we're trying */
	/* to position belongs.                                 */

    for (left_ptr = right_ptr - width;
         left_ptr >= base && compare (left_ptr, right_ptr) > 0;
         left_ptr -= width)
      ;

    left_ptr += width;
    memmove (left_ptr + width, left_ptr,    (size_t) (right_ptr - left_ptr));
    memcpy (left_ptr,         temp_record, width);
    } /* end for right_ptr */

  free (temp_record);
  return S_OK;
  }  /* end isort */