home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_11_07 / sortnet.c < prev    next >
C/C++ Source or Header  |  1993-02-04  |  2KB  |  83 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. int print_swaps;
  6. long n_swaps;
  7.  
  8. void show( int a, int b)
  9. {
  10.    if( print_swaps)
  11.       printf( "swap %d %d\n", a, b);
  12.    n_swaps++;
  13. }
  14.  
  15. long merge_sort( int n_elems)
  16. {
  17.    if( n_elems == 2)
  18.       return( 1L);
  19.    if( n_elems == 1)
  20.       return( 0L);
  21.    return( merge_sort( n_elems / 2) + merge_sort( n_elems - n_elems / 2)
  22.             + (long)n_elems - 1L);
  23. }
  24.  
  25. void bracket( int start1, int n_elem1, int start2, int n_elem2)
  26. {
  27.    if( n_elem1 == 1 && n_elem2 == 1)
  28.       show( start1, start2);
  29.    else if( n_elem1 == 1 && n_elem2 == 2)
  30.       {
  31.       show( start1, start2 + 1);
  32.       show( start1, start2);
  33.       }
  34.    else if( n_elem1 == 2 && n_elem2 == 1)
  35.       {
  36.       show( start1, start2);
  37.       show( start1 + 1, start2);
  38.       }
  39.    else
  40.       {
  41.       int a = n_elem1 / 2, b = (n_elem1 & 1) ? n_elem2 / 2 : (n_elem2 + 1) / 2;
  42.  
  43.       bracket( start1, a, start2, b);
  44.       bracket( start1 + a, n_elem1 - a, start2 + b, n_elem2 - b);
  45.       bracket( start1 + a, n_elem1 - a, start2, b);
  46.       }
  47. }
  48.  
  49.  
  50. void pstar( int start, int n_elem)
  51. {
  52.    if( n_elem > 1)
  53.       {
  54.       int m = n_elem / 2;
  55.  
  56.       pstar( start, m);
  57.       pstar( start + m, n_elem - m);
  58.       bracket( start, m, start + m, n_elem - m);
  59.       }
  60. }
  61.  
  62. void main( int argc, char **argv)
  63. {
  64.    double z = 0;
  65.    int i, n_elems = atoi( argv[1]);
  66.  
  67.    if( argc < 2)
  68.       {
  69.       printf( "SORTNET expects a number of elements as a command line\n");
  70.       printf( "argument.  Adding another argument will suppress printing\n");
  71.       printf( "the individual swaps and will give totals only.\n");
  72.       exit( 0);
  73.       }
  74.    print_swaps = (argc == 2);
  75.    pstar( 1, n_elems);
  76.    printf( "%ld swaps required\n", n_swaps);
  77.    for( i = 2; i <= n_elems; i++)
  78.       z += log( (double)i);
  79.    z = ceil( z / log( 2.));
  80.    printf( "Theoretical: %ld\n", (long)z);
  81.    printf( "Swaps for merge sort: %ld\n", merge_sort( n_elems));
  82. }
  83.