radtest.cpp

数据结构中排序的实例分析

// Radix sort main function for testing correctness of sort algorithm.
// To use: <radsortname> [+/-] <size_of_test> <bits>
//  + 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.
// <bits> controls the bits parameter for number of bits in radix

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <assert.h>
#include <time.h>
#ifdef UNIX
#include <sys/types.h>
#include <sys/times.h>
#include <sys/time.h>
#endif
#ifdef DOS
#include <bios.h>
#endif

#include "book.h"
typedef int ELEM;

long count1 = 0;
long count2 = 0;
int BITS = 1;

#define ARRAYSIZE 100

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

//#define print(X, Y)

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


int main(int argc, char** argv)
{
  ELEM* array;
  ELEM* 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> [<bits>]\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)
    BITS = atoi(argv[currarg]);
  if ((listsize > ARRAYSIZE) || (listsize < 0)) {
    cout << "Selected list size is too big\n";
    exit(-1);
  }
  cout << "Input: " << input << ", size: " << listsize << ", bits: "
       << BITS << "\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 << "Radix sort with list size " << listsize
       << " and bits " << BITS << "\n";
  printtime();
  return(0);
}