import java.util.Random;
import java.util.LinkedList;
import java.util.List;

import ucb.util.Stopwatch;

public class Sorter3 {
    
    public static void sort (List<Double> values) {
        for (int k = 1; k < values.size (); k += 1) {
            /* Elements 0 through k-1 are in nondecreasing order:
             *   values[0] <= values[1] <= ... <= values[k-1].
             * Insert element k into its correct position, so that
             *   values[0] <= values[1] <= ... <= values[k-1]. */
            double temp = values.get (k);
            int j;
            for (j = k - 1; j >= 0 && values.get (j) > temp; j -= 1) {
                values.set (j + 1, values.get (j));
            }
            values.set (j + 1, temp);
        }
    }
    
    public static void main (String [ ] args) throws Exception {
        if (args.length < 1) {
            System.err.println("Usage: java Sorter SIZE [TYPE [SEED]]");
            System.exit(1);
        }
        int n = Integer.parseInt(args[0]);
        String type = args.length >= 2 ? args[1] : "A";
        long seed = args.length >= 3 ? Long.parseLong (args[2]) : 42;
        Random R = new Random (seed);
        LinkedList<Double> values = new LinkedList<Double>();
        int k;
        for (k = 0; k < n; k += 1) {
            if (type.equals ("A"))
                values.add (R.nextDouble ());
            else
                values.add (k + 20.0 * R.nextDouble ()); 
        }
        Stopwatch t = new Stopwatch ( );
        t.start ( );
        sort (values);
        System.out.printf ("%5.3f seconds elapsed.%n", 
                           t.stop () * 1.0e-3);
        if (n < 20) {
            for (double x : values)
                System.out.println(x);
        }
    }
}