#include <iostream>
#include <string>
#include <vector>
#include <chrono>
#include <queue>
using namespace std;

//Let n be the number of items in A, n==A.size()
//run time: O(n)
//O(n) means that run time is <= c*n
void printList(vector<double> A)
{
	//total: is 3*n = O(n)
	for (int i = 0; i < A.size(); i++)//loops: n loops
	{
		cout << A[i] << endl; //3 operations.
	}
}

//Let n = end - start +1 (the number of items in range)
//run time: O(1) + O(1) + O(n) + O(1) = O(n)
int findSmallest(vector<double> &A, int start, int end)
{ //intial variable passing: O(1) 
	int smallest = start;  //O(1)

	//loop run time is: n*O(1) = O(n)
	for (int i = start; i <= end; i++) //loops: n 
	{
		if (A[i] < A[smallest]) // <= 4 = O(1)
			smallest = i;
	}
	
	return smallest; //O(1)
}

//Let n = X.size();
//Run time: O(n^2)
void selectionSort(vector<double> &X)
{
	//n*O(n) = O(n^2)
	for (int i = 0; i < X.size(); i++) //#loops: n
	{ //body: <= O(1) + O(n) = O(n)
		int smallest = findSmallest(X, i, X.size() - 1); //O(n)
		swap(X[i], X[smallest]); //O(1)
	}
}

//run time: O(n log n) + O(n log n) = O(n log n)
void heapSort(vector<double>& X)
{
	//step 0: declare a heap
	priority_queue<double> H;

	//step 1: n*O(log n) = O(n log n)
	for (int i = 0; i < X.size(); i++)//n loops
		H.push(X[i]); //O(log n)

	//step 2: n*(O(1)+O(log n) = O(n log n)
	for (int i = 0; i < X.size(); i++)//n loops
	{
		X[i] = H.top(); //O(1)
		H.pop();      //O(log n)
	}
}

int main()
{
	vector<double> X;

	X.push_back(15.3);		//At index 0
	X.push_back(8);			//1
	X.push_back(568);		//2
	X.push_back(45);		//3
	X.push_back(3.14);		//4
	X.push_back(93.7);		//5
	X.push_back(703);		//6
	X.push_back(57);		//7
	X.push_back(347.2);		//8
	X.push_back(1.5);		//9
	X.push_back(752);		//10
	X.push_back(57);		//11
	X.push_back(12);		//12
	X.push_back(53);		//13

	//Warmup:
	//Print the list
	printList(X);
	cout << endl;

	//Challenge #2:
	//Search list for smallest item:
	//return the index of smallest in specified range

	cout << findSmallest(X, 0, X.size() - 1) << endl;  //9
	cout << findSmallest(X, 5, 8) << endl;   //7
	cout << endl << endl;


	//Challenge #3
	//Sort the list
	//selectionSort(X);
	heapSort(X);

	printList(X);  //should now be sorted
	cout << endl;

	//Stress test with large list
	int hugeNumber = 1000000;
	vector<double> large;

	for (int i = 0; i < hugeNumber; i++)
		large.push_back(rand());

	auto start = chrono::high_resolution_clock::now();
	//selectionSort(large);
	heapSort(large);
	auto finish = chrono::high_resolution_clock::now();

	chrono::duration<double> elapsed = finish - start;
	cout << "Algorithm took: " << elapsed.count() << endl;

	//printList(large);

	return 0;
}

///Timing code
/*
auto start = chrono::high_resolution_clock::now();
//method to time...
auto finish = chrono::high_resolution_clock::now();

chrono::duration<double> elapsed = finish - start;
cout << "Algorithm took: " << elapsed.count() << endl;
*/