mrgtest.cpp

经典c++程序的实现

// Mergesort main function for testing correctness of sort algorithm.
// To use: <mrgsortname> [+/-] <size_of_test> <threshold>
//  + means increasing values, - means decreasing value and no
//    parameter means random values;
// <size_of_test> controls the size of an individual test out
// of an array of size ARRAYSIZE.  For example, inssort 10 will run
// a series of sorts on lists of size 10.
// <threshold> controls the threshold parameter for certain sorts, e.g.,
//   cutoff point for quicksort sublists.

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <assert.h>
#include <time.h>
/*
#include <sys/types.h>
#include <sys/times.h>
#include <sys/time.h>
*/

#include "..\include\book.h"

long count1 = 0;
long count2 = 0;
int THRESHOLD = 0;

#define ARRAYSIZE 100

void sort(int* array, int* tp, int listsize);

//#define print(X, Y)

void print(int* array, int listsize) {
  for(int i=0; i<listsize; i++)
    cout << array[i] << " ";
  cout << "\n";
}


int main(int argc, char** argv)
{
  int* array;
  int* tp;
  int i;
  int listsize;
  int currarg;
  int input = 0;  // Type to sort: -1 -- descending; +1 - ascending;
                  //                0 -- random values

  inittime();

  Randomize();

  array = new int[ARRAYSIZE];
  tp = new int[ARRAYSIZE+1];

  if ((argc < 2) || (argc > 4)) {
    cout << "Usage: <sortname> [+/-] <size> [<threshold>]\n";
    exit(-1);
  }
  currarg = 1;
  if (argv[currarg][0] == '-') {
    input = -1;
    currarg++;
  }
  else if (argv[currarg][0] == '+') {
    input = 1;
    currarg++;
  }
  listsize = atoi(argv[currarg++]);
  if (argc > currarg)
    THRESHOLD = atoi(argv[currarg]);
  if (listsize > ARRAYSIZE) {
    cout << "Selected list size is too big\n";
    exit(-1);
  }
  cout << "Input: " << input << ", size: " << listsize << ", threshold: "
       << THRESHOLD << "\n";

  if (input == -1)
    for (i=0; i<ARRAYSIZE; i++)
      array[i] = ARRAYSIZE - i;  // Reverse sorted
  else if (input == 0)
    for (i=0; i<ARRAYSIZE; i++)
      array[i] = Random(32003);  // Random
  else
    for (i=0; i<ARRAYSIZE; i++)
      array[i] = i;              // Sorted

  starttime();
  for (i=0; i<ARRAYSIZE; i+=listsize) {
    sort(&array[i], tp, listsize);
    print(&array[i], listsize);
  }
  stoptime();
  cout << "Merge Sort with list size " << listsize
       << " and threshold " << THRESHOLD << "\n";
  printtime();
  cout << "Count1 is " << count1 << ", Count2 is " << count2 << "\n";
  return(0);
}