/**
 *  Exercise recursive formulations of sorting algorithms

 *  @author:  Timothy Rolfe

 *  Just exercising code, so everything is static or local.
 */
import java.io.*;
import java.util.StringTokenizer;

class ArraySort
{//Random generator is seeded in main, but used in shuffle.
   static java.util.Random generator = new java.util.Random();

/**
 * Recursive insertion sort --- NOT the recommended formulation ! ! !
 */
   public static void insSort ( Comparable[] x, int n )
   {  int  lim = n-1,             // last entry in the array
           hole;                  // insertion point in sorted region
      Comparable save = x[lim];   // Item being positioned

      if ( n > 1 )
      {  insSort ( x, n-1 );      // Recursively sort the front end
      // Position save between x[lim] and x[0]
         for ( hole = lim ;
               hole > 0 && save.compareTo(x[hole-1]) < 0 ;
               hole-- )
         {  x[hole] = x[hole-1];  }

         x[hole] = save;          // Plug the hole with save
      } // if ( n > 1 )
   // else is ignored --- array of 0 or 1 entries is already sorted
   } // end insSort()

/**
 * Recursive selection sort --- NOT the recommended formulation ! ! !
 */
   public static void selSort ( Comparable[] x, int size )
   {  if ( size > 1 )
      {  int j = maxIdx ( x, size ); // Subscript of largest entry

         swap ( x, size-1, j );      // Move to end of the array
         selSort ( x, size-1 );      // Recursively sort the front end
                                     // NOTE:  tail recursion, easy optim.
      } // end if ( size > 1 )
   // else is ignored --- array of 0 or 1 entries is already sorted
   } // end selSort()

/**
 * Find the subscript of the largest entry.  Used by selSort()
 */
   private static int maxIdx ( Comparable[] x, int n )
   {  int big = 0,    // Subscript of largest encountered
          k;          // Loop variable

      for ( k = 1; k < n; k++ ) // Start at 1 --- no need to check 0
         if ( x[big].compareTo(x[k]) < 0 )   // I.e., NOT the biggest so far
            big = k;
      return big;
   } // end maxIdx()

/**
 * Swap two array entries.  Used by selSort()
 */
   private static void swap ( Comparable[] x, int p, int q )
   {  Comparable t = x[p];  x[p] = x[q];  x[q] = t;  }

   static BufferedReader console = new BufferedReader
                                  (new InputStreamReader(System.in));
   static StringTokenizer tk = new StringTokenizer("");

/**
 * Return one line from System.in
 */
   static String readLine()
   {  String rtn = "";

      try
      {  rtn = console.readLine();  }
      catch (Exception e)
      {  System.out.println(e);  System.exit(-1);  }
      return rtn;
   }

   static int readInt()
   {
      try
      {
         while (tk.countTokens() == 0 )
            tk = new StringTokenizer(readLine());
         return Integer.parseInt(tk.nextToken());
      }
      catch (Exception e)
      {  System.out.println(e);  System.exit(-1);  }
      return Integer.MIN_VALUE;
   }

/**
 * Driving main to exercise the algorithms.
 */
   public static void main ( String [] args )
   {  Integer [] test;                      // Array of int objects
      int        size;                      // control outer loop
      long seed = generator.nextLong();     // Same sequence in all three

      System.out.print ("Array length:  ");
      if ( args.length < 1 )
         size = readInt();
      else
      {  size = Integer.parseInt(args[0]);
         System.out.println ("" + size);
      } // end if/else regarding args[0]

      test = new Integer [size];

      fillArray ( test );
      System.out.println ("Initial state:");
      generator.setSeed(seed);
      shuffleArray ( test, size );
      showArray ( test, size );

   // Array sort method from java.util.Arrays
      java.util.Arrays.sort( test, 0, size );
      if ( !sorted ( test, size ) )
      {  System.out.println("util.Arrays.sort failed.  Abort!");
         System.exit(1);
      }
      System.out.println ("After util.Arrays.sort:");
      showArray ( test, size );

   // Selection sort
      System.out.println ("\nInitial state:");
      generator.setSeed(seed);
      shuffleArray ( test, size );
      showArray ( test, size );
      selSort ( test, size );
      if ( !sorted ( test, size ) )
      {  System.out.println("util.Arrays.sort failed.  Abort!");
         System.exit(2);
      }
      System.out.println ("After selSort:");
      showArray ( test, size );

   // Insertion sort
      System.out.println ("\nInitial state:");
      generator.setSeed(seed);
      shuffleArray ( test, size );
      showArray ( test, size );
      insSort ( test, size );
      if ( !sorted ( test, size ) )
      {  System.out.println("util.Arrays.sort failed.  Abort!");
         System.exit(3);
      }
      System.out.println ("\nAfter insSort:");
      showArray ( test, size );

   } // end main()

// Utility functions related to non-sorting operations:

/**
 * Fill the array with increasing sequence starting at 1
 */
   private static void fillArray ( Integer [] x )
   {  for ( int k = 0; k < x.length; k++ )
         x[k] = new Integer(k+1);
   } // end fillArray()
/**
 * Shuffle the entire array, using the class scope generator
 */
   public static void shuffleArray ( Comparable [] x, int lim )
   {  while ( lim > 1 )
      {  int item;
         Comparable save = x[lim-1];
         item = generator.nextInt(lim);
         x[--lim] = x[item];                // Note predecrement on lim
         x[item] = save;
      } // end while
   } // end shuffleArray()
/**
 * Display in lines of 10 values
 */
   private static void showArray ( Integer [] x, int lim )
   {  int k;

      for ( k = 0; k < lim; k++ )
      {  StringBuffer front = new StringBuffer("       ");
         String       back  = "" + x[k].intValue();
         front.setLength(front.length()-back.length());
         System.out.print (front+back);
         if ( (k+1) % 10 == 0 )
            System.out.println("");
      } // end for
      if ( k % 10 != 0 )
         System.out.println("");
      System.out.print ("\t\tPress <Enter> to continue:  ");
      pause();
   } // end showArray()
/**
 * Verify that the array is correctly sorted
 */
   private static boolean sorted ( Comparable[] x, int n )
   {  for ( int k = 1; k < n; k++ )
         if ( x[k-1].compareTo(x[k]) > 0 )
            return false;
      return true;
   } // end sorted()


/**
 * Wait for keyboard entry of '\n', discarding all input up to '\n'
 */
   public static void pause()
   {  try
      {  while ( System.in.read() != '\n' ) ;  }
      catch (java.io.IOException e)
      {  System.out.println (e);  System.exit(-1);  }
   } // end pause()
} // end ArraySort class