#include <iostream>
#include <string>
using namespace std;

/*
//static array declaration
double A[10];


//dynamic array declaration
double* A;
A = new double[10];
*/

//Print out items in X from start to end
//Let n = end - start + 1
//Run time: O(n)
void display(double * X, int start, int end)
{
	for (int i = start; i <= end; i++)
	{
		cout << X[i] << endl;
	}
}

//Run time: O(n)
void randomFill(double* X, int start, int end, int maxNum)
{
	for (int i = start; i <= end; i++)
	{
		X[i] = rand() % maxNum + 1;
	}
}


//Locate position of value key within given
//search range.  Return the index location.
//Return -1 if key is not present in given
//range.
//Run time: O(n)
int find(double* X, int start, int end, double key)
{
	for (int i = start; i <= end; i++)
	{
		if (X[i] == key)
			return i;
	}
	return -1;
}

//Return index of smallest value
//in given range.
//Run time: O(n)
int findSmallest(double* X, int start, int end)
{
	int smallSeenSoFarIndex = start;

	for (int i = start; i <= end; i++)
	{
		if (X[i] < X[smallSeenSoFarIndex])
			smallSeenSoFarIndex = i;
	}
	return smallSeenSoFarIndex;
}

//Run time: O(n^2)
void selectionSort(double* X, int start, int end)
{
	for (int i = start; i <= end; i++) //n loops
	{
		//Body run time: O(n)
		int smallIndex = findSmallest(X, i, end);
		swap(X[i], X[smallIndex]);
	}
}

int main()
{
	double* A;
	//An array of 10 doubles.
	A = new double[10];

	A[0] = 3.14;
	A[1] = 2.7;
	A[2] = 1.6;
	A[3] = 186282;
	A[4] = 6.6;
	A[5] = 15;
	A[6] = 17;
	A[7] = 11;
	A[8] = 9.3;
	A[9] = 7.4;

	//Challenge Ultimate:
	selectionSort(A, 0, 9);
	display(A, 0, 9);
	cout << endl;

	//Challenge #1: write a display method

	//prints all 10
	display(A, 0, 9);
	cout << endl;

	//prints 186282, 6.6, 15, 17, 11
	display(A, 3, 7);
	cout << endl;

	//prints 9.3, 7.4
	display(A, 8, 9);
	cout << endl;


	//Challenge #2: write a random fill method (fill with
	//random numbers from 1-1000.
	double* B;
	B = new double[5];

	randomFill(B, 0, 4, 10);
	//randomFill(A, 3, 7, 1000);

	display(B, 0, 4);
	cout << endl;

	display(A, 3, 7);
	cout << endl;


	//Challenge #3: write a search routine
	cout << find(A, 0, 9, 6.6) << endl;  //4
	cout << find(A, 2, 7, 17) << endl; //6
	cout << find(A, 3, 7, 3.14) << endl; //-1 (it's not there)

	/*

	///QUIZ
	double* C = new double[4];
	C[0] = 5;
	C[1] = 15;
	C[2] = 3;
	c[3] = 2;

	cout << addEmUp(C, 0, 3) << endl; //25
	cout << addEmUp(C, 2, 3) << endl; //5
	cout << addEmUp(C, 0, 2) << endl; //23


	//Challenge #4: write a "find smallest" search routine


	//Challenge #5: write a sorting routine

*/
	return 0;
}