/** Example:  because the program WORKS doesn't mean you're finished.
 *
 *  Problem:  Given an array, transform it so that no entry is preceeded
 *            by an element that tests as coming _after_ itself.
 *  Utility methods:
 *     boolean sorted  --- true if the above condition is met.
 *     void    shuffle --- randomly rearrange the contents of the array
 *  Language:  Java version 5 --- nanoTime, printf, and autoboxing
 *  @author [perpetrator]  Timothy Rolfe
 */
public class DumbSort
{//Random number generator used by shuffle
   private static java.util.Random gen = new java.util.Random();

   /**
    * main to exercise the sorting algorithm
    */
   public static void main ( String[] args )
   {  int n, nFinal;
      java.util.Scanner console = new java.util.Scanner( System.in );

      // Allow for command-line arguments:
      System.out.print ("Initial N:  ");
      if ( args.length > 0 )
      {  n = Integer.parseInt(args[0]);
         System.out.println ( n );
      }
      else
         n = console.nextInt();
      System.out.print ("  Final N:  ");
      if ( args.length > 1 )
      {  nFinal = Integer.parseInt(args[1]);
         System.out.println ( nFinal );
      }
      else
      {  nFinal = console.nextInt();
         console.nextLine();  // Move past '\n'
      }

      for ( ; n <= nFinal ; n++ )
      {  double       start, elapsed;
         Comparable[] x = new Integer[n];

         // Timing is ONLY of the shuffle/sort, not of the initialization
         for ( int k = 0; k < n; k++ )
            x[k] = k+1;
         start = System.nanoTime();
         // Average over 1000 random arrays
         for ( int pass = 0; pass < 1000; pass++ )
         {  shuffle ( x );
            sort ( x );
         }
         elapsed = ( System.nanoTime() - start ) * 1.0E-09;
         System.out.printf ("Size %2d:  %3.3f msec. on average\n",
            n, elapsed);
         System.out.flush();      // Force console output
      }
   }

   /**
    * sort     Rearrange x so that no element is out of order
    *
    * @param   x  Array to be sorted
    */
   public static void sort ( Comparable[] x )
   {  while ( ! sorted(x) )  shuffle(x);  }

   /**
    * sorted    Determine whether the array is sorted.
    *
    * @param    x  Array to be tested
    * @return   false if any element in x is out of order, else true
    */
   private static boolean sorted ( Comparable[] x )
   {  for ( int j = 1; j < x.length; j++ )
         if ( x[j-1].compareTo ( x[j] ) > 0 )    // I.e., comes AFTER
            return false;
      return true;      // NOTHING was out of place
   }

   /**
    * shuffle  Randomize position of all array elements
    *
    * @param   x  Array to be shuffled
    */
   private static void shuffle ( Object[] x )
   {  for ( int n = x.length ; n > 1 ; )
      {  int    k = gen.nextInt(n--);  // Note post-decrement
         Object temp = x[k];

         x[k] = x[n];
         x[n] = temp;
      }
   }
}

/*  Specimen run:
Initial N:  3
  Final N:  10
Size  3:  0.005 msec. on average
Size  4:  0.006 msec. on average
Size  5:  0.044 msec. on average
Size  6:  0.330 msec. on average
Size  7:  2.804 msec. on average
Size  8:  25.066 msec. on average
Size  9:  256.527 msec. on average
Size 10:  2864.344 msec. on average
*/