import java.util.Random;
import java.util.Scanner;

public class ShufflingExample{

    final static int NUM_REPETITIONS  = 5;

    /** Swaps two items, basedh on their indices.
     * @pre x and y are the indices of the items to be swapped.
     * @post Contents of actual locations that x and y represent are swapped.
     * @param a Array of items
     * @param i1 Index of a given data item
     * @param i2 Index of a given data item
     */
    public static void swap(int[] a, int i1, int i2){
        int temp = a[i1];
        a[i1] = a[i2];
        a[i2] = temp;
    }  // end swap


    /** Finds the largest item in an array.
     * @pre a is an array of items
     * @post None.
     * @param a  Array of items
     * @param n Largest position of array a to use
     * @return The index of the largest item in the array (from indicies 0..n-1). The arguments are unchanged. */
    public static int indexOfLargest(int[] a, int n){
        int indexSoFar = 0;  // index of largest item
        // found so far
        for( int currentIndex = 1; currentIndex < n; ++currentIndex){
            // Invariant: a[indexSoFar] >= a[0..currentIndex-1]
            if( a[currentIndex] > a[indexSoFar] ){
                indexSoFar = currentIndex;
            }
        }  // end for

        return indexSoFar;  // index of largest item
    }  // end indexOfLargest

    /** Sorts the items in the keyArray into ascending order and performs the same
     *  rearrangements on otherArray.
     * @pre keyArray is an array of n items.
     * @post The array keyArray is sorted into ascending order and the contents of
     *       otherArray are potentially rearranged; n is unchanged.
     * @param keyArray  The array to sort
     * @param otherArray Another array to perform the sorting operations on.
     * @param n  The size (or at least the portion to sort) of both keyArray and otherArray.
     */
    public static void sort2Arrays(int[] keyArray, int[] otherArray, int n){
        // last = index of the last item in the subarray of
        //        items yet to be sorted,
        // largest = index of the largest item found

        for( int last = n-1; last >= 1; --last){
            // Invariant: keyArray[last+1..n-1] is sorted and is >= theArray[0..last]

            // select largest item in keyArray[0..last]
            int largest = indexOfLargest(keyArray, last+1);

            // swap largest item keyArray[largest] with keyArray[last]
            // Perform the same sway on otherArray
            swap( keyArray, largest, last);
            swap( otherArray, largest, last);
        }  // end for
    }  // end selectionSort


    // Make a secondary array and assign random numbers to it
    // Sort the random numbers at the same time as the array
    public static void shuffle1(int[] array, Random rand){

        int[] randomValues = new int[ array.length ];
        for( int i = 0; i < array.length; i++){
            randomValues[i] = rand.nextInt();
        }

        sort2Arrays( randomValues, array, array.length);
    }

    // For each location in the array, choose a random location to swap it with
    // Assumes srand() has already been called
    public static void shuffle2(int[] array, Random rand){
        int randIndex = -1;

        for( int i = 0; i < array.length; i++){
            randIndex = Math.abs(rand.nextInt()) % array.length;
            swap( array, i, randIndex );
        }
    }


    public static void main( String[] args ){

        long begin, end; // time in milliseconds

        /* initialize random seed: */
        Random rand = new Random();

        Scanner stdinScanner = new Scanner( System.in );

        int maxN = -1;
        while( maxN <= 0 ){
            try{
                System.out.print("Enter the maximum value of N: ");
                maxN = stdinScanner.nextInt();
            }catch(Exception e){
                System.err.println("Error retrieving a whole number from input");
                stdinScanner.next(); // skip over invalid token
            }
        }

        System.err.println( "\tShuffle1\tShuffle2" );
        System.err.println( "n\t(ms)\t(ms)" );

        for(int n = 10; n <= maxN; n *= 10){
            System.err.print( n );

            int[] array = new int[n];

            // measure how much time it takes
            int timeElapsed = 0;
            for( int j = 0; j < NUM_REPETITIONS; j++){

                // populate each element of the array with its index
                for( int i = 0; i < n; i++){
                    array[i] = i;
                }

                begin = System.currentTimeMillis();
                shuffle1( array, rand);
                end = System.currentTimeMillis();
                timeElapsed += end - begin;
            }
            System.err.print( "\t" + timeElapsed );


            timeElapsed = 0;
            for( int j = 0; j < NUM_REPETITIONS; j++){

                // populate each element of the array with its index
                for( int i = 0; i < n; i++){
                    array[i] = i;
                }

                begin = System.currentTimeMillis();
                shuffle2( array, rand);
                end = System.currentTimeMillis();
                timeElapsed += end - begin;
            }
            System.err.println( "\t" + timeElapsed );
        }
    }
}