home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1986 / 03 / wissbaum.mar < prev   
Text File  |  1986-03-31  |  3KB  |  92 lines
  1. /*                                                                         */
  2. /*        Bose-Nelson Sort - Recursive Version                             */
  3. /*                                                                         */
  4. /*        by R J Wissbaum                                                  */
  5. /*      15553 E Wyoming Dr - H                                             */
  6. /*      Aurora, CO       80012                                             */
  7. /*                                                                         */
  8. /*   Reference:                                                            */
  9. /*           Dr. Dobb's Journal                                            */
  10. /*           September 1985 (#107)                                         */
  11. /*      Page 68                                                            */
  12. /*                                                                         */
  13. /*                                                                         */
  14. #include "STDIO.H"
  15.  
  16. int count = 0;
  17.  
  18. main ( argc, argv )
  19. int argc,*argv;
  20. { int n;
  21.    char arg[255];
  22.    if ( argc <2 )
  23.       { printf ( "USAGE: bose5 n >outfile \n" );
  24.         exit();
  25.       }
  26.    else
  27.       { getarg( 1, arg, 255, argc, argv );
  28.         n = atoi( arg );
  29.         if ( n<0 ) n = -n;
  30.         bosesort ( 2, 1, n, 0, 0 );
  31.      printf ( "There were %d swaps \n", count );
  32.       }
  33. }
  34. bosesort( n, i, x, j, y )
  35. int n, i, x, j, y;
  36. { int a, b;
  37.   switch ( n )
  38.   {
  39.   case 0:  { /* printf ( "}\n" ); */
  40.            }
  41.            break;
  42.  
  43.   case 1:  { /*   printf ( "swap ( %d, %d ); \n", i, x ); */
  44.               count++;
  45.            }
  46.            break;
  47.  
  48.   case 2:  {  if ( x != 1 )
  49.              {  a = ( x / 2 );
  50.             bosesort ( 3, i, a, (i+a), (x-a) );
  51.             bosesort ( 2, (i+a), (x-a), 0, 0 );
  52.             bosesort ( 2, i, a, 0, 0 );
  53.                  }
  54.            }
  55.        break;
  56.  
  57.   case 3:  {  a = ( x / 2 );
  58.               if      ( even ( x ) )  b = ( y + 1 ) / 2;
  59.               else                    b = ( y / 2 );
  60.  
  61.               if      ( ( x == 1 ) && ( y == 1 ) )  bosesort ( 1, i, j, 0, 0 );
  62.               else if ( ( x == 1 ) && ( y == 2 ) ) 
  63.                        {
  64.                    bosesort ( 1, i, j, 0, 0 );
  65.                      bosesort ( 1, i, (j+1), 0, 0 );
  66.                    }
  67.               else if ( ( x == 2 ) && ( y == 1 ) )
  68.                    {
  69.                    bosesort ( 1, (i+1), j, 0, 0 );
  70.                    bosesort ( 1, i, j, 0, 0 );
  71.                        }
  72.           else if ( ( x != 0 ) && ( y != 0 ) )
  73.                    {
  74.                    bosesort ( 3, (i+a), (x-a), j, b );
  75.                    bosesort ( 3, (i+a), (x-a), (j+b), (y-b) );
  76.                    bosesort ( 3, i, a, j, b );
  77.                    }
  78.            }
  79.            break;
  80.   default: {
  81.            printf ( "FATAL: Error in stack \n" );
  82.            exit ();
  83.            }
  84.            break;
  85.  
  86.   }  /*  End of WHILE loop */
  87. }    /*  End of BOSESORT   */
  88.  
  89. even ( x )
  90. int x;
  91.   { return ( 1 - (1 & x ) ); }
  92.  bre