binsimp.cpp

经典c++程序的实现

#include <iostream.h>
#include <stdlib.h>

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

typedef int ELEM;
#include "..\include\swap.h"

void permute(int *array, int n) {
  for (int i=n; i>0; i--)
    swap(array[i-1], array[Random(i)]);
}

#define COUNT 100

int main(int argc, char** argv) {
  ELEM* A; // The array pointer
  ELEM* B; // Second array
  int n;
  int i, j;

  if(argc != 2) {
    cout << "Usage: binsimp <size_of_array>\n";
    exit(-1);
  }

  n = atoi(argv[1]);
  if ((A = (ELEM *)calloc(n, sizeof(ELEM))) == NULL) {
    cout << "Error: Unable to allocate space for array\n";
    exit(-1);
  }
  if ((B = (ELEM *)calloc(n, sizeof(ELEM))) == NULL) {
    cout << "Error: Unable to allocate space for second array\n";
    exit(-1);
  }

  Randomize();

  for (i=0; i<n; i++)
    A[i] = i;
  permute(A, n);

  inittime();

  starttime();
  for (j=0; j<COUNT; j++) {
  for (i=0; i<n; i++)
     B[key(A[i])] = A[i];
  }
  stoptime();

  cout << "Time for `fast' binsort (" << COUNT << " runs)\n";
  printtime();

  // For "slow" binsort, we first get a benchmark on the time to
  // do permutations.

  starttime();
  for (j=0; j<COUNT; j++) {
    for (i=0; i<n; i++)
      A[i] = i;
    permute(A, n);
  }
  stoptime();

  cout << "Time to do " << COUNT << " permutations:\n";
  printtime();

  // Now, we do the binsort.

  starttime();
  for (j=0; j<COUNT; j++) {
    for (i=0; i<n; i++)
      A[i] = i;
    permute(A, n);
  for (i=0; i<n; i++)
     while (key(A[i]) != i)
        swap(A[i], A[key(A[i])]);
  }
  stoptime();

  cout << "Time for `slow' binsort (" << COUNT << " runs)\n";
  printtime();

  cout << "Don't forget to subtract the permutations from total time!\n";

  cout << "Let's check to be sure this works.\n";
  for(i=0; i<10; i++)
    cout << A[i] << "  ";
  cout << "\n";
  for(i=0; i<10; i++)
    cout << B[i] << "  ";
  cout << "\n";

 return 0;
}