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 >
C/C++ Source or Header  |  1993-02-04  |  4KB  |  127 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  4. #include <math.h>
  5. #include <time.h>
  6.  
  7. #define RANDOM 1
  8. #define ASCENDING 2
  9. #define DESCENDING 3
  10.  
  11. static long n_compared;
  12.  
  13. int my_shellsort( char *data, unsigned n_elements, unsigned esize,
  14.                      int (*compare)(void *elem1, void *elem2));
  15. int my_qsort( char *data, unsigned n_elements, unsigned element_size,
  16.                      int (*compare)(void *elem1, void *elem2));
  17. int my_mergesort( void *data, unsigned n_elements, unsigned elem_size,
  18.                      int (*compare)(void *elem1, void *elem2));
  19.  
  20. int compare_func( void *elem1, void *elem2)
  21. {
  22.    int rval = 0;
  23.  
  24.    if( *(unsigned *)elem1 < *(unsigned *)elem2)
  25.       rval = -1;
  26.    if( *(unsigned *)elem1 > *(unsigned *)elem2)
  27.       rval = 1;
  28.    n_compared++;
  29.    return( rval);
  30. }
  31.  
  32. void main( int argc, char **argv)
  33. {
  34.    unsigned *numbers, n_elems, n_swap = 0, i;
  35.    int order = ASCENDING;
  36.    double theoretic_min = 0.;
  37.  
  38.    if( argc < 3)
  39.       {
  40.       printf( "SORTTEST expects a letter giving the sort type to be used\n");
  41.       printf( "followed by a number of elements to sort.  For example:\n\n");
  42.       printf( "sorttest m 10000\n\n");
  43.       printf( "would test mergesorting of 10000 elements,  tell you how many\n");
  44.       printf( "compares were required,  and how this compares with the\n");
  45.       printf( "ceil( log(n!) / log(2.)) limit.\n\n");
  46.       printf( "Sorts available are m(erge), q(uick) (the built-in version),\n");
  47.       printf( "k(wick) (the version in QSORT.C), and s(hell).  By default,\n");
  48.       printf( "the elements are in ascending order;  you can add the\n");
  49.       printf( "following arguments to change this:\n\n");
  50.       printf( "r    Elements are in random order\n");
  51.       printf( "d    Elements are in descending order\n");
  52.       printf( "s15  Fifteen pairs of elements are swapped randomly\n\n");
  53.       printf( "If,  for example,  you wanted to test quicksort on 1000 elements\n");
  54.       printf( "in descending order,  except for two pairs swapped at random,\n");
  55.       printf( "you would use:\n\nsorttest q 1000 d s2\n");
  56.       exit( 0);
  57.       }
  58.    srand( (unsigned)time( NULL));
  59.    n_elems = atoi( argv[2]);
  60.    for( i = 2; (int)i < argc; i++)
  61.       switch( argv[i][0])
  62.          {
  63.          case 'r': case 'R':
  64.             order = RANDOM;
  65.             break;
  66.          case 's': case 'S':
  67.             n_swap = atoi( argv[i] + 1);
  68.             break;
  69.          case 'd': case 'D':
  70.             order = DESCENDING;
  71.             break;
  72.          }
  73.    numbers = calloc( n_elems, sizeof( unsigned));
  74.    switch( order)
  75.       {
  76.       case RANDOM:
  77.          for( i = 0; i < n_elems; i++)
  78.             numbers[i] = rand( );
  79.          break;
  80.       case ASCENDING:
  81.          for( i = 0; i < n_elems; i++)
  82.             numbers[i] = i;
  83.          break;
  84.       case DESCENDING:
  85.          for( i = 0; i < n_elems; i++)
  86.             numbers[i] = n_elems - i;
  87.          break;
  88.       }
  89.    for( i = 0; i < n_swap; i++)
  90.       {
  91.       unsigned a = rand( ) % n_elems, b = rand( ) % n_elems;
  92.  
  93.       unsigned temp = numbers[a];
  94.       numbers[a] = numbers[b];
  95.       numbers[b] = temp;
  96.       }
  97.  
  98.    printf( "Array set up...\n");
  99.    n_compared = 0L;
  100.    switch( argv[1][0])
  101.       {
  102.       case 'q': case 'Q':
  103.          qsort( numbers, n_elems, sizeof( unsigned), compare_func);
  104.          break;
  105.       case 'k': case 'K':
  106.          my_qsort( numbers, n_elems, sizeof( unsigned), compare_func);
  107.          break;
  108.       case 's': case 'S':
  109.          my_shellsort( numbers, n_elems, sizeof( unsigned), compare_func);
  110.          break;
  111.       case 'm': case 'M':
  112.          my_mergesort( numbers, n_elems, sizeof( unsigned), compare_func);
  113.          break;
  114.       }
  115.    printf( "Sorted: %ld compares made\n", n_compared);
  116.    for( i = 0; i < n_elems - 1; i++)
  117.       if( numbers[i] > numbers[i + 1])
  118.          {
  119.          printf( "ARRAY NOT CORRECTLY SORTED!\n");
  120.          exit( 0);
  121.          }
  122.    for( i = 2; i <= n_elems; i++)
  123.       theoretic_min += log( (double)i);
  124.    theoretic_min = ceil( theoretic_min / log( 2.));
  125.    printf( "Theoretic min: %ld\n", (long)theoretic_min);
  126. }
  127.