/*
 * QuadraticSort.java
 *
 */
import java.util.Random;
import java.util.Date;

public class QuadraticSort {
    
   final static int DEFAULT_ELEMENT_NUM=30000; 
    
   public static void main (String[] args) {
      int i, j, tmp;
      int[] a;
      int n;  /* the number of elements in the array */ 
      if (args.length == 0)
          n = DEFAULT_ELEMENT_NUM;
      else
          n = Integer.parseInt(args[0]);
      a = new int[n];       
      /* set the initial value randomly for a */
      Random r = new Random();
      for (i=0; i< a.length; i++) {
        a[i] =  r.nextInt(n);
      }

      /* get the starting time */
      Date start = new Date();

      /* quadratic sort */
      for (i=0; i<a.length-1; i++) {
          for (j=i+1; j<a.length; j++) {
              if(a[i] > a[j]) {
                  /* switch a[i] and a[j] */
                  tmp = a[i];
                  a[i] = a[j];
                  a[j] = tmp;
              }
          }
      }

      /*get the ending time */
      Date end = new Date();
      System.out.println("The running time is "+ (end.getTime()-start.getTime()) + " milliseconds");
      
      /* here we only select 10 elements in sorted array to print*/
      for (i=0; i < a.length; i+= a.length/10) {
          System.out.print(a[i] +" ");
      }
      System.out.println();
  }
}