Category : Files from Magazines
Archive : CUJ9307.ZIP
Filename : SORTTEST.C
Output of file : SORTTEST.C contained in archive : CUJ9307.ZIP
#include
#include
#include
#include
#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);
}
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/