mlsort.c

不同的排序算法的源程序

/***********************************************************************/
/*  SORT(): Non-Recursive Merge List 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/List sort.  Fast, but uses even more space than msort. */
/* Like merge sort, but takes advantage of any preexisting ordered sublists. */

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

#include "sort.h"

#define ENDLIST -1
#define VERBOSE (0)

static char *base;
static unsigned int nelem, width;
static int (*compare) (void *, void *);
static int merge (int left, int right);
static void show_lists (int *lists, int nlists);
static void show_list (int list);

static int  *next;  /* array: which element comes after this one? */

int
mlsort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
{
  int *lists; /* array of pointers to sorted sublists */
  unsigned int nlists, list_num;
  int elem_num, temp_num;
  char *temp_base;
  int workspace_size;
  void *workspace;  /* contains lists or temp_base, depending on when */

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

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

  workspace_size = nelem * max (sizeof (*lists) + sizeof (*next), width);
  workspace = malloc (workspace_size);
  if (workspace == NULL)
	return S_NOMEM;

  temp_base = workspace;
  lists = workspace;     /* it's never used concurrently with temp_base! */

  next = malloc (nelem * sizeof (*next));
  if (next == NULL)
	return S_NOMEM;

  lists[0] = 0;
  nlists = 1;

  for (elem_num = 1;
       elem_num < nelem;
       elem_num++)
  {
    if (compare(base + (elem_num - 1) * width,
		base + elem_num * width) > 0)
    {
      next [elem_num - 1] = ENDLIST;
      lists [nlists] = elem_num;
      nlists++;
      }
    else
    {
      next [elem_num - 1] = elem_num;
      }
    } /* end for */
  next [nelem - 1] = ENDLIST;

  while (nlists > 1)
  {  /* Merge pairs of lists */
    for (list_num = 0;
	 list_num < (nlists - 1);
	 list_num++, nlists--)
    {
#if VERBOSE
      show_lists (lists, nlists);
      printf ("\nMerging list %d with list %d:\n", list_num, list_num + 1);
#endif
      lists[list_num] = merge (lists[list_num], lists[list_num + 1]);
      lists[list_num + 1] = lists[nlists - 1];
      } /* end for */
    } /* end while */

#if VERBOSE
  show_lists (lists, nlists);
#endif

  /* move everything to where it belongs. */

  for (elem_num = 0, temp_num = lists[0];
       elem_num < nelem;
       elem_num++, temp_num = next [temp_num])
  {
    memcpy (temp_base + width * elem_num, base + width * temp_num, width);
    }

  memcpy (base, temp_base, width * nelem);

  return S_OK;
  }  /* end msort */


int
merge (int left, int right)
{
  int first, last;
  char *left_ptr, *right_ptr;

  left_ptr = base + left * width;
  right_ptr = base + right * width;

  if (compare (left_ptr, right_ptr) > 0)
  {
    first = last = right;
    right = next [right];
    right_ptr = base + right * width;
    }
  else
  {
    first = last = left;
    left = next [left];
    left_ptr = base + left * width;
    }

  while (left != ENDLIST && right != ENDLIST)
  {
    if (compare (left_ptr, right_ptr) > 0)
    {
      /* right is smaller; use it */
      next [last] = right;
      last = right;
      right = next [right];
      right_ptr = base + right * width;
      }
    else
    {
      /* left is smaller; use it */
      next [last] = left;
      last = left;
      left = next [left];
      left_ptr = base + left * width;
      }
    }

  next [last] = (left == ENDLIST) ? right : left;

  return first;
  } /* end merge */


void
show_lists (int *lists, int nlists)
{
  int list;

  for (list = 0;
       list < nlists;
       list++)
  {
    printf ("List # %d at ", list);
    show_list (lists [list]);
    } /* end for */
  } /* end show_lists */


#pragma warn -use
void
show_list (int list)
{
  int node;

  printf ("%d: ", list);
  for (node = list;
       node != ENDLIST;
       node = next [node])
  {
    printf ("# %d: %.4lf, ", node, *((double *) (base + node * width)));
    }
  printf ("\n");
  } /* end show */