home *** CD-ROM | disk | FTP | other *** search
/ ActiveX Programming Unleashed CD / AXU.iso / jgl_1_1 / benchmarks / sortingbenchmarks.java < prev    next >
Encoding:
Java Source  |  1996-07-12  |  2.9 KB  |  121 lines
  1. import jgl.*;
  2.  
  3. public class SortingBenchmarks
  4.   {
  5.   static Randomizer random = new Randomizer();
  6.   static final int LOOPS = 100;
  7.   static final int MAX_SIZE = 3000;
  8.  
  9.   public static void main( String args[] )
  10.     {
  11.     System.out.println( "SortingBenchmarks" );
  12.     Benchmark handcodeBenchmark = new Benchmark( "handcoded sorting", 5 );
  13.     Benchmark jglBenchmark = new Benchmark( "jgl sort algorithm", 5 );
  14.  
  15.     for( int i = 0; i < LOOPS; i++ )
  16.       {
  17.       int size = Randomizer.getInt( MAX_SIZE );
  18.       String data[] = new String[ size ];
  19.       for( int j = 0; j < size; j++ )
  20.         data[ j ] = getRandomString();
  21.  
  22.       String data1[] = new String[ size ];
  23.       System.arraycopy( data, 0, data1, 0, size );
  24.       jglBenchmark.start();
  25.       jglSort( data1 );
  26.       jglBenchmark.stop();
  27.  
  28.       String data2[] = new String[ size ];
  29.       System.arraycopy( data, 0, data2, 0, size );
  30.       handcodeBenchmark.start();
  31.       handcodeSort( data2 );
  32.       handcodeBenchmark.stop();
  33.       }
  34.  
  35.     jglBenchmark.compareTo( handcodeBenchmark );
  36.     }
  37.  
  38.   static String getRandomString()
  39.     {
  40.     int len = Randomizer.getInt( 30 );
  41.     StringBuffer buffer = new StringBuffer();
  42.     for( int i = 0; i < len; i++ )
  43.       buffer.append( (char) ( ((int) 'a')+ Randomizer.getInt( 0, 25 ) ) );
  44.     return buffer.toString();
  45.     }
  46.  
  47.   static void jglSort( String data[] )
  48.     {
  49.     Sorting.sort( new ObjectArray( data ), new LessString() );
  50.     }
  51.  
  52.   static void handcodeSort( String data[] )
  53.     {
  54.     quickSort( data, 0, data.length - 1, new GreaterString() );
  55.     }
  56.  
  57.   static void quickSort( String data[], int lo, int hi, BinaryPredicate predicate )
  58.     {
  59.     if( lo >= hi ) 
  60.       return;
  61.  
  62.     int mid = ( lo + hi ) / 2;
  63.  
  64.     if( predicate.execute( data[ lo ], data[ mid ] ) )
  65.       {
  66.       String tmp = data[ lo ];
  67.       data[ lo ] = data[ mid ];
  68.       data[ mid ] = tmp;
  69.       }
  70.  
  71.     if( predicate.execute( data[ mid ], data[ hi ] ) )
  72.       {
  73.       String tmp = data[ mid ];
  74.       data[ mid ] = data[ hi ];
  75.       data[ hi ] = tmp;
  76.  
  77.       if( predicate.execute( data[ lo ], data[ mid ] ) )
  78.         {
  79.         String tmp2 = data[ lo ];
  80.         data[ lo ] = data[ mid ];
  81.         data[ mid ] = tmp2;
  82.         }
  83.       }
  84.  
  85.      int left = lo + 1;
  86.      int right = hi - 1;
  87.  
  88.      if( left >= right ) 
  89.        return; 
  90.  
  91.      String partition = data[ mid ];
  92.  
  93.      for( ;; ) 
  94.       {
  95.       while( predicate.execute( data[ right ], partition ) )
  96.         {
  97.         --right;
  98.         }
  99.  
  100.       while( left < right && !predicate.execute( data[ left ], partition ) )
  101.         {
  102.         ++left;
  103.         }
  104.  
  105.       if( left < right )
  106.         {
  107.         String tmp = data[ left ];
  108.         data[ left ] = data[ right ];
  109.         data[ right ] = tmp;
  110.         --right;
  111.         }
  112.       else
  113.         {
  114.         break;
  115.         }
  116.       }
  117.  
  118.     quickSort( data, lo, left, predicate );
  119.     quickSort( data, left + 1, hi, predicate );
  120.     }
  121.   }