home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The C Users' Group Library 1994 August
/
wc-cdrom-cusersgrouplibrary-1994-08.iso
/
listings
/
v_11_07
/
sorttest.c
< prev
next >
Wrap
C/C++ Source or Header
|
1993-02-04
|
4KB
|
127 lines
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <math.h>
#include <time.h>
#define RANDOM 1
#define ASCENDING 2
#define DESCENDING 3
static long n_compared;
int my_shellsort( char *data, unsigned n_elements, unsigned esize,
int (*compare)(void *elem1, void *elem2));
int my_qsort( char *data, unsigned n_elements, unsigned element_size,
int (*compare)(void *elem1, void *elem2));
int my_mergesort( void *data, unsigned n_elements, unsigned elem_size,
int (*compare)(void *elem1, void *elem2));
int compare_func( void *elem1, void *elem2)
{
int rval = 0;
if( *(unsigned *)elem1 < *(unsigned *)elem2)
rval = -1;
if( *(unsigned *)elem1 > *(unsigned *)elem2)
rval = 1;
n_compared++;
return( rval);
}
void main( int argc, char **argv)
{
unsigned *numbers, n_elems, n_swap = 0, i;
int order = ASCENDING;
double theoretic_min = 0.;
if( argc < 3)
{
printf( "SORTTEST expects a letter giving the sort type to be used\n");
printf( "followed by a number of elements to sort. For example:\n\n");
printf( "sorttest m 10000\n\n");
printf( "would test mergesorting of 10000 elements, tell you how many\n");
printf( "compares were required, and how this compares with the\n");
printf( "ceil( log(n!) / log(2.)) limit.\n\n");
printf( "Sorts available are m(erge), q(uick) (the built-in version),\n");
printf( "k(wick) (the version in QSORT.C), and s(hell). By default,\n");
printf( "the elements are in ascending order; you can add the\n");
printf( "following arguments to change this:\n\n");
printf( "r Elements are in random order\n");
printf( "d Elements are in descending order\n");
printf( "s15 Fifteen pairs of elements are swapped randomly\n\n");
printf( "If, for example, you wanted to test quicksort on 1000 elements\n");
printf( "in descending order, except for two pairs swapped at random,\n");
printf( "you would use:\n\nsorttest q 1000 d s2\n");
exit( 0);
}
srand( (unsigned)time( NULL));
n_elems = atoi( argv[2]);
for( i = 2; (int)i < argc; i++)
switch( argv[i][0])
{
case 'r': case 'R':
order = RANDOM;
break;
case 's': case 'S':
n_swap = atoi( argv[i] + 1);
break;
case 'd': case 'D':
order = DESCENDING;
break;
}
numbers = calloc( n_elems, sizeof( unsigned));
switch( order)
{
case RANDOM:
for( i = 0; i < n_elems; i++)
numbers[i] = rand( );
break;
case ASCENDING:
for( i = 0; i < n_elems; i++)
numbers[i] = i;
break;
case DESCENDING:
for( i = 0; i < n_elems; i++)
numbers[i] = n_elems - i;
break;
}
for( i = 0; i < n_swap; i++)
{
unsigned a = rand( ) % n_elems, b = rand( ) % n_elems;
unsigned temp = numbers[a];
numbers[a] = numbers[b];
numbers[b] = temp;
}
printf( "Array set up...\n");
n_compared = 0L;
switch( argv[1][0])
{
case 'q': case 'Q':
qsort( numbers, n_elems, sizeof( unsigned), compare_func);
break;
case 'k': case 'K':
my_qsort( numbers, n_elems, sizeof( unsigned), compare_func);
break;
case 's': case 'S':
my_shellsort( numbers, n_elems, sizeof( unsigned), compare_func);
break;
case 'm': case 'M':
my_mergesort( numbers, n_elems, sizeof( unsigned), compare_func);
break;
}
printf( "Sorted: %ld compares made\n", n_compared);
for( i = 0; i < n_elems - 1; i++)
if( numbers[i] > numbers[i + 1])
{
printf( "ARRAY NOT CORRECTLY SORTED!\n");
exit( 0);
}
for( i = 2; i <= n_elems; i++)
theoretic_min += log( (double)i);
theoretic_min = ceil( theoretic_min / log( 2.));
printf( "Theoretic min: %ld\n", (long)theoretic_min);
}