#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <algorithm>

using namespace std;
int selectionSort(vector<int> &v);
int insertionSort(vector<int> &v);
void printVector(vector<int> &v);

int main()
{

    vector<int> myVector;       // to hold 100 values in a vector
    int numCount, numCount2=0;         // to hold comparison numbers

    // Get random numbers for vector
    srand(time(0));
    for(int i=0; i<100; i++)
    {
    myVector.push_back(rand()%90+10);
    }

    // Make copy of myVector values into myVector2 to use for insertion sorting
    vector<int> myVector2(myVector);

    // Print Original Vector
    cout << "Original vector: ";
    printVector(myVector);

    // Call selectionSort to sort the original vector and return # of comparisons into numCount
    numCount = selectionSort(myVector);


    // Print the original vector sorted by selection sort
    cout << endl << endl << "Vector After Selection Sort: ";
    printVector(myVector);

    // Print # of comparisons for selection sort
    cout << endl << endl << "Number of comparisons: numcount= " << numCount;

    // Call insertionSort to sort the 2nd original vector copy and return # of comparisons into numCount
    numCount2 = insertionSort(myVector2);

    // Print the original vector sorted by insertion sort
    cout << endl << endl << "Vector after Insertion Sort: ";
    printVector(myVector2);

    // Print # of comparisons for insertion sort
    cout << endl << endl << "Number of comparisons numCount2: " << numCount2;

    // Format
    cout << endl << endl;
    cout << "-----------------------------------------------------------------------------" << endl;

    // Reverse the original vector after being sorted by selectionSort(myVector)
    reverse(myVector.begin(), myVector.end());

    // Reverse the 2nd vector copy to be used for insertion sorting
    reverse(myVector2.begin(), myVector2.end());

    // Print original vector in reverse order. Note: it is not sorted at this time.
    cout << endl << "Vector in reverse order: ";
    printVector(myVector);

    // Call selectionSort to sort the reverse vector and return the # of comparisons into numCount
    numCount = selectionSort(myVector);

    // Print reverse original vector sorted by selectionSort
    cout << endl << endl << "Vector after Selection Sort: ";
    printVector(myVector);

    // Print # of comparisons used by selectionSort
    cout << endl << endl << "Number of comparisons: " << numCount;

    // Call insertionSort to sort the 2nd copy of reverse vector and return # of comparisons into numCount
    numCount = insertionSort(myVector2);

    // Print the 2nd copy of reverse vector sorted by insertionSort
    cout << endl << endl << "Vector after Insertion Sort: ";
    printVector(myVector2);

    // Print # of comparisons used by insertionSort
    cout << endl << endl << "Number of comparisons: " << numCount;
    cout << endl << endl;
    return 0;
}

/*************************************************************************************************
Function definition: the void printVector function takes a vector as its arguments and prints the
contents of the vector by using a C++11 range based for-loop.
**************************************************************************************************/
void printVector(vector<int> &v)
{

    for (int val: v)
    {
        cout << val << " ";
    }
}

/*******************************************************************************************
Function definition: the selectionSort function takes a vector as its arguments and sorts
the contents of the vector in ascending order with a selection sort algorithm. The function
will return the counter for number of comparisons it makes.
********************************************************************************************/

int selectionSort(vector<int> &v)
{
    //pos_min is short for position of min
	int pos_min,temp, counter=0;

	for (int i=0; i < v.size()-1; i++)
	{
	    pos_min = i;//set pos_min to the current index of array

		for (int j=i+1; j < v.size(); j++)
		{
        //counter++; // tracking # of comparisons
		if (v[j] < v[pos_min])
        {
        pos_min=j;
        counter++;  // tracking # of comparisons
        }


	//pos_min will keep track of the index that min is in, this is needed when a swap happens
		}

	//if pos_min no longer equals i than a smaller value must have been found, so a swap must occur
        if (pos_min != i)
        {

        temp = v[i];
        v[i] = v[pos_min];
        v[pos_min] = temp;
        }

	}
return counter;

}

/*********************************************************************************************
Function definition: the insertionSort function takes a vector as its arguments and sorts the
contents of the vector in ascending order with an insertion sort algorithm. The function will
return the counter for number of comparisons it makes.
*********************************************************************************************/
int insertionSort (vector<int> &v){
	 	int j, temp, counter = 0;

	for (int i = 1; i < v.size(); i++){
		j = i;

		while (++counter && j > 0 && v[j] < v[j-1]){
		//while ( j > 0 && v[j] < v[j-1]){
			  temp = v[j];
			  v[j] = v[j-1];
			  v[j-1] = temp;
			  j--;


			  }
			  //cout << "counter=  " << " -  " << counter;
		}
return counter;
}