msort.c

不同的排序算法的源程序

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

/* Merge sort.  Fast, but uses lots of space. */

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

#include "sort.h"

#define VERBOSE (0)

static char *base, *last_ptr, *temp_base;
static unsigned int nelem, width;
static int (*compare) (void *, void *);
static void merge (char *, unsigned int);
#if VERBOSE
static void show_array (void *, int);
#endif

int
msort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
{
  long sublist_length, sublist_offset;
  unsigned int list_size;

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

#if VERBOSE
  printf ("Msort (%p, %d, %d, %p).\n", pbase, pnelem, pwidth, pcompare);
#endif

  list_size = nelem * width;

  temp_base = malloc (list_size);
  if (temp_base == NULL)
	return S_NOMEM;

  last_ptr = base + list_size - width;

  /* We first merge sublists of length 1, then of length 2, and */
  /* so on, doubling each time.                                 */

  for (sublist_length = width;
       sublist_length < list_size;
       sublist_length <<= 1)
  {
    for (sublist_offset = 0;
         sublist_offset + sublist_length < list_size;
         sublist_offset +=  sublist_length << 1)
#pragma warn -sig
       merge (base + sublist_offset, (unsigned int) sublist_length);
#pragma warn .sig
     } /* for sublist_length */

  free (temp_base);

  return S_OK;
  }  /* end msort */


void
merge (char *left_base, unsigned int length)
{
  char *left_ptr, *right_ptr, *left_max, *right_max, *result_ptr;

#if VERBOSE
  printf ("Merge (%p, %u)\n", left_base, length);
#endif

  left_ptr = left_base;
  right_ptr = left_base + length;
  left_max = right_ptr - width;
  right_max = (length > last_ptr - right_ptr) ? last_ptr : left_max + length;

#if VERBOSE
  fputs ("Input: ", stdout);
  show_array (left_base, (right_max - left_base + width) / sizeof (double));

  if (length > 20000)
    printf ("Merging %p - %p with %p - %p.\n",
          left_ptr, left_max, right_ptr, right_max);
#endif


  result_ptr = temp_base;
  while (1)
  {
    if (compare (left_ptr, right_ptr) > 0)
    {
      memcpy (result_ptr, right_ptr, width);
      right_ptr += width;
      result_ptr += width;
      if (right_ptr > right_max)
      {
        memcpy (result_ptr, left_ptr, left_max - left_ptr + width);
        break;
        }
      }
    else
    {
      memcpy (result_ptr, left_ptr, width);
      left_ptr += width;
      result_ptr += width;
      if (left_ptr > left_max)
      {
        memcpy (result_ptr, right_ptr, right_max - right_ptr + width);
        break;
        }
      }
    }  /* end while */


#if VERBOSE
  printf ("Copying %d bytes from %p to %p.\n",
          right_max - left_base + width, temp_base, left_base);
  fputs ("Intermediate: ", stdout);
  show_array (temp_base, (right_max - left_base + width) / sizeof (double));
#endif

  memcpy (left_base, temp_base, right_max - left_base + width);

#if VERBOSE
  fputs ("Output: ", stdout);
  show_array (left_base, (right_max - left_base + width) / sizeof (double));
#endif

  } /* end merge */