import java.util.Random;

public final class SelectionTest {

   private static final Random RNG =
      new Random (Long.getLong ("seed", System.nanoTime()));

   public static double timeTrialsSelection (final int t, int n) {
      double total = 0.0;
      int[] a = new int [n];
      for (int i=0; i<t; i++) {
         for (int j=0; j<n; j++) a[i]= RNG.nextInt ();
         final double start = System.nanoTime();
         Selection.select(a);
         total += (System.nanoTime()-start);
      }
      return total;
   }

   public static double timeTrialsInsertion (final int t, int n) {
      double total = 0.0;
      int[] a = new int [n];
      for (int i=0; i<t; i++) {
         for (int j=0; j<n; j++) a[i]= RNG.nextInt ();
         final double start = System.nanoTime();
         Insertion.insertSort(a);
         total += (System.nanoTime()-start);
      }
      return total;
   }

   public static double timeTrialsQuick (final int t, int n) {
      double total = 0.0;
      int[] a = new int [n];
      for (int i=0; i<t; i++) {
         for (int j=0; j<n; j++) a[i]= RNG.nextInt ();
         final double start = System.nanoTime();
         Quick.quickSort(a, 0, a.length);
         total += (System.nanoTime()-start);
      }
      return total;
   }
   
   public static void main (final String[] args) {
      final int t = Integer.parseInt (args[0]);
      double prevS = timeTrialsSelection (t, 512);
      double prevI = timeTrialsInsertion (t, 512);
      for (int i=1024; i<100_000; i+=i) {
         final double timeS = timeTrialsSelection (t, i);
         final double timeI = timeTrialsInsertion (t, i);
         System.out.printf ("%,8d %4.2f %4.2f%n", i, timeS/prevS, timeI/prevI);
         prevS = timeS; prevI = timeI;
      }
   }
}