/* CH-231-A
   Selection_Sort.cpp
   Nathan Kassa
   [email protected]
*/

#include<iostream>
#include<chrono>
#include <fstream>
using namespace std;
using namespace std::chrono;

// implementing a swap function

template<typename T>
void swappp(T& x, T& y) {
    T temp;
    temp = x;
    x = y;
    y = temp;    
}

int * randommm(int n){
    srand(time(NULL));
    int *arr = new int[n];
    for(int i = 0; i < n; i++) {
        arr[i] = rand() % n; // the modulus operator insures that the random number wont exceed n
    }
    return arr;
}

// selection sort algorithm
template<typename T> 
void Selectionsort1(T * arr, int n) {
    for(int i = 0; i < n-1; i++) {
        int min = i;
        for(int j = i+1; j < n; j++) {
            if(arr[min] > arr[j]) {
                min = j;
            }
        }
        if( min != i) {
            swappp<T>(arr[min], arr[i]);
        }
    }
}

// function to print the sorted array
template<typename T>
void print(T *arr, int size) {
    for(int i = 0; i < size; i++) {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}


int main() {
    // checking the if the implemented algorithm works.
    //int * arr2;
    ofstream out;
    out.open("INPUT.txt");
    cout<<"Checking if the implemented algorithm works using an already supplied sequence.\n";
    int arr[] = {64,25,12,22,11};
    //float arr1[] = {0.001,1.23,2.31,2.31,0.501,0.302,4.0};
    int *arr1;
    int size = 5;
    Selectionsort1<int>(arr,size);
    //Selectionsort1<float>(arr1,7);
    cout<<"Sorted array: ";
    print(arr,size);
    //cout<<"Sorted float array: ";
    //print(arr1,7);
    cout<<"Implementation executed in integers and floats. The output below is for part c and d of the problem.\n";
    cout<<"part c:\n";
    for(int size = 0; size < 1000; size +=5) {
    // case A: corresponding to the most number of swaps. Not necessarily a decreasingly sorted array but one with the largest element at the first position
        arr1 = randommm(size);
        arr[0] = size; // making the first element the largest
        auto start = high_resolution_clock::now();
        Selectionsort1(arr,size);
        auto stop = high_resolution_clock::now();
        auto worstcase = duration_cast<microseconds>(stop-start);
        // case B: Best case which is an already sorted array
        // passing the previously sorted array to the selection sort and measuring the time again
        auto start1 = high_resolution_clock::now();
        Selectionsort1(arr,size);
        auto stop1 = high_resolution_clock::now();
        auto bestcase = duration_cast<microseconds>(stop1-start1);
        // average case
        double sum = 0;
        for(int i = 0; i < 5; i++) {
            arr1 = randommm(size);
            auto start2 = high_resolution_clock::now();
            Selectionsort1(arr,size);
            auto stop2 = high_resolution_clock::now();
            auto total = duration_cast<microseconds>(stop2-start2);
            sum = sum + total.count();
        }
        double average_case = 0.0;
        average_case = sum/5;
        out<<size<<" "<<(double)worstcase.count()<<" "<<(double)bestcase.count()<<" "<<average_case<< endl;

    }
    out.close();
    return 0;
}