/**
 * Sorter.java
 *
 * @author Jeff Ondich, 2/10/04
 */

class Sorter
{
    /**
     * Using N specified on the command line, main generates
     * a random permutation of the integers 1,2,...,N-1,
     * prints them (if N is less than 30), sorts them
     * using one of the algorithms implemented below, and
     * then prints them again (again if N is less than 30).
     * Finally, main prints the time it took to do the sorting.
     */
    public static void main( String[] args )
    {
        if( args.length == 0 )
        {
            System.out.println( "Usage: java Sorter numberOfIntegersToSort" );
            System.exit( 1 );
        }

        final int   nItems = java.lang.Integer.parseInt( args[0] );
        int[]       theItems = new int[nItems];

        shuffle( theItems );

        if( nItems < 30 )
            printArray( theItems );

        long startTime = System.currentTimeMillis();
        insertionSort( theItems );
        long endTime = System.currentTimeMillis();

        if( nItems < 30 )
            printArray( theItems );

        //System.out.println( "Sorting time for " + nItems
         //               + " items: " + (endTime-startTime) + " ms" );
        //System.out.println( "" );
    }

    /**
    * Generates a random permutation of the integers
    * 1,2,...,a.length-1.  See p. 139 of "Seminumerical
    * Algorithms, 2nd edition,"  by Donald Knuth, for
    * more details.
    *
    * @param  a  the array to be filled with integers
    */
    public static void shuffle( int[] a )
    {
        int k;
        for( k=0; k < a.length; k++ )
            a[k] = k;

        for( k=a.length-1; k > 0; k-- )
        {
            int swapIndex = (int)Math.floor( Math.random() * (k+1) );
            int temp = a[k];
            a[k] = a[swapIndex];
            a[swapIndex] = temp;
        }
    }

	/**
	 * Prints the elements of the specified array to standard
     * output, separated by spaces.
     *
     * @param  a  the array to be printed
	 */
	public static void printArray( int[] a )
	{
		for( int i=0; i < a.length; i++ )
			System.out.print( a[i] + " " );
		System.out.println( "" );
	}


    /**
    * Sorts the specified array into increasing order
    * using the Insertion Sort algorithm.
    *
    * @param  a  the array to be sorted
    */
    public static void insertionSort( int[] a )
    {
        int     j, k;
        int     temp;

        for( j=1; j < a.length; j++ )
        {
            temp = a[j];
            for( k=j-1; k >= 0  &&  temp < a[k]; k-- )
                a[k+1] = a[k];
            a[k+1] = temp;
        }
    }

    /**
    * Sorts the specified array into increasing order
    * by building a binary search tree from the array
    * elements, and then doing an in-order traversal
    * of the tree.
    *
    * @param  a  the array to be sorted
    */
    public static void bstSort( int[] a )
    {
    }
}