#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */
#include <iostream>
#include "sort2arrays.h"

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

// calculate the difference in between clock2 and clock1 (in milliseconds) 
double diffclock(clock_t clock1, clock_t clock2){
    double diffticks = clock1 - clock2;
    double diffms = (diffticks * 1000) / CLOCKS_PER_SEC;
    return diffms;
}



// Make a secondary array and assign random numbers to it
// Sort the random numbers at the same time as the array
// Assumes srand() has already been called
void shuffle1(int* array, int count){
    
    int* randomValues = new int[ count];
    for( int i = 0; i < count; i++){
        randomValues[i] = rand();
    }

    sort2Arrays( randomValues, array, count);

    delete[] randomValues;
}

// For each location in the array, choose a random location to swap it with
// Assumes srand() has already been called
void shuffle2(int* array, int count){
    int randIndex = -1;
    
    for( int i = 0; i < count; i++){
        randIndex = rand() % count;
        swap( array[i], array[ randIndex]);
    }
}

#define NUM_REPETITIONS 5

int main(int argc, char* argv[]){

    clock_t begin, end;
    
    /* initialize random seed: */
    srand( time(NULL));

    int maxN = -1;
    do{ 
        cout << "Enter the maximum value of N: ";
        cin >> maxN;
    }while( ! cin );

    cerr << "n\tShuffle1\tShuffle2\n";

    for(int n = 10; n <= maxN; n *= 10){
        cerr << n;

        //int array[n]; // works for ~1,000,000, won't work for large 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 = clock();
            shuffle1( array, n);
            end = clock();
            timeElapsed += diffclock( end, begin);
        }
        cerr << '\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 = clock();
            shuffle2( array, n);
            end = clock();
            timeElapsed += diffclock( end, begin);
        }
        cerr << '\t' << timeElapsed;
        cerr << '\n';
    
        delete[] array;
    }
    return 0;
}