testsort.c

不同的排序算法的源程序

/***********************************************************************/
/*  TESTSORT: Sort Tester/Analyzer program                             */
/*  See the function declaration for calling information.              */
/*  Program is by Bruce Feist; please contact me at any of the below   */
/*  if you have any questions, problems, or comments.                  */
/*  CompuServe: 71320,3635; use Easyplex, BPROGB, or MACDEV            */
/*  Enlightened Bulletin Board: [phone], N/8/1                  */
/*                                                                     */
/* Feel free to make use of this code in your own programs.            */
/***********************************************************************/

#define FALSE 0
#define TRUE 1
#define VERBOSE FALSE

#include <stdio.h>
#include <process.h>
#include <alloc.h>
#include <stdlib.h>
#include <mem.h>
#include <string.h>
#include <conio.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>

#include "sort.h"

typedef int cmpfunc(const void *, const void *);

cmpfunc comp;
void more (void);
void show_array (double *, int);
static int qusort (void *, int, int, int());
double drand (void);


void
main()
{
  double *list, bias;
  int n_entries, entry_number, display;
  long  start_time, stop_time;
  char sort_type;
  int (*sort)(void *base, size_t nelem, size_t width, cmpfunc comp);

  while (TRUE)
  {
    printf ("Enter the number of entries to be sorted: ");
    fflush (stdout);
    scanf ("%d", &n_entries);
    if (n_entries <= 0)
      exit(0);
    list = malloc (n_entries * sizeof (double));
    if (list != NULL)
      break;
	printf ("Insufficient memory.  Please choose a smaller size.\n");
	}

  do
  {
    puts ("Biases can range from -1 to 1; they do not have to be integers.");
    puts ("-1 is reverse sorted, 0 is random, and 1 is sorted.");
    printf ("Your desired bias is:  ");
    scanf ("%lf", &bias);
    } while (bias < -1 || bias > 1);

  printf ("Display the list generated?  (y or n):  ");
  while (TRUE)
  {
    display = toupper (getch());
    if (display == 'Q')
    {
      puts ("Quit");
      exit (0);
      }
    if (display == 'Y' || display == 'N')
      break;
    printf ("\aEnter y or n:  ");
    }
  display = (display == 'Y');
  puts (display ? "Yes" : "No");

  printf ("I)nsertion, S)hell's, M)erge, merge L)ist, Q)uick, or H)eapsort?  ");
  do
  {
    sort_type = toupper (getch ());
    switch (sort_type)
    {
#pragma warn -sus
      case 'I': sort = isort;
		puts ("Insertion");
		break;
      case 'M': sort = msort;
		puts ("Merge");
		break;
      case 'Q': sort = qusort;
		puts ("Quick");
		break;
      case 'H': sort = hsort;
		puts ("Heap");
		break;
      case 'S': sort = ssort;
		puts ("Shell's");
		break;
      case 'L': sort = mlsort;
		puts ("Merge List");
		break;
#pragma warn .sus
      default:
		sort = NULL;
		putchar ('\a');
		break;
      } /* end switch */
    } while (sort == NULL);

  printf ("\nInitializing list");

  for (entry_number = 0;
       entry_number < n_entries;
       entry_number++)
  {
    if ((entry_number * 60 / n_entries) > ((entry_number-1) * 60 / n_entries))
      printf (".");
    list[entry_number] = entry_number * bias + drand();
    } /* end for */

  printf ("\n");
  if (display)
    show_array (list, n_entries);

#if FALSE
  more();
#endif

  puts ("Sorting. . .");
  time (&start_time);
  if ((*sort) (list, n_entries, sizeof (list[0]), comp) != S_OK)
  {
    puts ("Unable to perform sort.");
    }

  time (&stop_time);

  puts ("Done sorting.");
  if (display)
    show_array (list, n_entries);

  printf ("Verifying sort");
  for (entry_number = 1;
       entry_number < n_entries;
       entry_number++)
  {
    if ((entry_number * 60 / n_entries) > ((entry_number-1) * 60 / n_entries))
      printf (".");
    if (comp(list + entry_number - 1, list + entry_number) > 0 &&
	comp(list + entry_number, list + entry_number - 1) < 0)
      printf ("\nSort error: # %d (%lf) > # %d (%lf).\n",
	      entry_number - 1, list[entry_number-1],
	      entry_number, list[entry_number]);
    } /* end verification loop */
  printf ("\n");

  printf ("Time elapsed: %ld seconds.\n", stop_time - start_time);

  exit (0);
  }


int
comp (const void *i, const void *j)
{
  register int retcode;

  retcode = (*(double *) i < *(double *)j) ? -1 : 1;
#if VERBOSE
  printf ("comp (%p: 1.4lf, %p: %1.4lf) = %d.\n", i, *(double *) i,
	j, *(double *) j, retcode);
#endif
  return retcode;
  }


void
show_array (double *list, int n_entries)
{
  int entry;

  for (entry = 0;
       entry < n_entries;
       entry++)
    printf ("%lf ", list [entry]);
  printf ("\n");
  }


double
drand (void)
{  /* Returns a random number from 0 to 1. */

  return (random (1000) / 1000.0);

  } /* end drand */


int
qusort (void *base, int nelem, int width, int compare())
{
  qsort (base, nelem, width, compare);
  return S_OK;
  }  /* end qusort */