Australian Personal Computer 1998 December/apc3111.iso/workshop/rsort.cpp

C/C++ Source or Header | 1998-10-04 | 4.9 KB | 215 lines

/*****************************************************************/
/* RSORT.CPP                                                     */
/*                                                               */
/* Radix sort code plus testbed                                  */
/*                                                               */
/* (c) 1998 Emmenjay Consulting Pty Ltd                          */
/*                                                               */
/* History                                                       */
/* 05/10/98 MJS  Initial Coding                                  */
/*                                                               */
/*****************************************************************/


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

// GENERIC DATA CLASS USED FOR SORTING.  MAY EASILY BE MODIFIED
// FOR PRACTICAL USE
class data_t {
  private:
    unsigned long k;
  public:
    unsigned long key( void )
      { return k; }
    data_t& operator =(unsigned long newk)
      { k=newk; return *this; }
    unsigned bits( unsigned ndx, unsigned num )
      { return (k>>ndx) & ~(~0<<num); }
};

// DEFINE VARIOUS OPERATORS USED IN TESTING
ostream& operator <<( ostream& os, data_t d )
{
  return os << d.key();
}

int operator <( data_t d1, data_t d2 )
{
  return d1.key()<d2.key();
}

int operator >( data_t d1, data_t d2 )
{
  return d1.key()>d2.key();
}

int operator ==( data_t d1, data_t d2 )
{
  return d1.key()==d2.key();
}


// GENERIC ROUTINE TO SWAP TWO DATA ELEMENTS
void swap( data_t& a, data_t& b )
{
  data_t c=a;
  a = b;
  b = c;
}

// RADIX EXCHANGE SORT ROUTINE
// a is an array of data
// l is the left index into a
// r is the right index into a
// b is the bit on which we are currently sorting
void rexch( data_t a[], int l, int r, int b )
{
  if (r>l && b>=0) {
    int ir =r;
    int il =l;
    while (il<ir) {
      while (!a[il].bits(b,1) && il<ir) il++;
      while (a[ir].bits(b,1) && il<ir) ir--;
      swap( a[il], a[ir] );
    }
    if (!a[r].bits(b,1)) ir++;
    rexch( a, l, ir-1, b-1 );
    rexch( a, ir, r, b-1 );
  }
}

// WRAPPER FOR RADIX EXCHANGE SORT
void resort( data_t a[], int num )
{
  rexch( a, 0, num-1, 31 );
}


// STRAIGHT RADIX SORT
#define m 8   /* number of bits to look at at once */
#define M 256 /* 2**m */
#define w 32  /* bits in key */

void rssort( data_t a[], int N )
{
  int i, ipass;
  int count[M];
  data_t *b = new data_t[N];

  for (ipass = 0; ipass < w/m; ipass++) {
    for (i = 0; i <  M; i++) count[i] = 0;
    for (i = 0; i < N; i++)
      count[a[i].bits(ipass*m, m)]++;
    for (i = 1; i <  M; i++)
      count[i] += count[i-1];
    for (i = N-1; i >= 0; i--)
      b[--count[a[i].bits(ipass*m, m)]] = a[i];
    for (i = 0; i < N; i++) a[i] = b[i];
  }
  delete b;
}

// SLOW BUBBLE SORT
void bsort( data_t a[], int num )
{
  for (int i=1; i<num; i++)
    for (int j=i; j>0; j--)
      if (a[j-1].key() > a[j].key())
        swap( a[j-1], a[j] );
}

// PARTITION ROUTINE FOR QUICK SORT
int partition(data_t a[], int l, int r)
{
  int i = l-1, j = r; data_t v = a[r];
  for (;;) {
    while (a[++i] < v) ;
    while (v < a[--j]) if (j == l) break;
    if (i >= j) break;
    swap(a[i], a[j]);
  }
  swap(a[i], a[r]);
  return i;
}

// GENERIC QUICK SORT
void quicksort(data_t a[], int l, int r)
{
  if (r <= l) return;
  int i = partition(a, l, r);
  quicksort(a, l, i-1);
  quicksort(a, i+1, r);
}

// WRAPPER FOR QUICK SORT
void qsort(data_t a[], int N)
{
  quicksort( a, 0, N-1 );
}


// NUMBER OF KEYS TO SORT
#define MAX 250000

// DATA TO SORT
static data_t a[MAX];


int main( void )
{
  clock_t start, end;
  int i;

  printf( "Sorting %d values\n", MAX );

  srand( 1 );
  for (i=0; i<MAX; i++) {
    a[i] = rand()*rand();
  }
  start = clock();
  resort( a, MAX );
  end = clock();
  printf( "Radix Exchange Sort took %.3f seconds\n",
          (double)(end-start)/CLOCKS_PER_SEC );

  srand( 1 );
  for (i=0; i<MAX; i++) {
    a[i] = rand()*rand();
  }
  start = clock();
  rssort( a, MAX );
  end = clock();
  printf( "Straight Radix Sort took %.3f seconds\n",
          (double)(end-start)/CLOCKS_PER_SEC );

  srand( 1 );
  for (i=0; i<MAX; i++) {
    a[i] = rand()*rand();
  }
  start = clock();
  qsort( a, MAX );
  end = clock();
  printf( "Quick Sort took %.3f seconds\n",
          (double)(end-start)/CLOCKS_PER_SEC );

// OMITTED BUBBLE SORT AS IT IS TOO SLOW
//  srand( 1 );
//  for (i=0; i<MAX; i++) {
//    a[i] = rand()*rand();
//  }
//  start = clock();
//  bsort( a, MAX );
//  end = clock();
//  printf( "Bubble Sort took %.3f seconds\n",
//          (double)(end-start)/CLOCKS_PER_SEC );

//  for (i=0; i<MAX; i++)
//    cout << a[i] << ' ';
//  cout << '\n';

  return 0;
}