#include <iostream>
#include <string>
#include <chrono>  //has stuff to time code
using namespace std;

//print items in given array from start index to end.
//O(n) run time
//This is linear run time.
void printItems(double A[], int start, int end)
{
	for (int i = start; i <= end; i++)
		cout << A[i] << endl;
}


//Run time:  Let n = end - start + 1.
//Run time: O(n), means run time <= c*n
//This is linear run time.
int locateSmallest(double A[], int start, int end)
{
	int smallIndex = start;
	for (int i = start+1; i <= end; i++)
	{
		if (A[i] < A[smallIndex])
		{
			smallIndex = i;
		}
	}

	return smallIndex;
}

//Selection Sort.
//Let n = end - start + 1.
//Run time: n loops times O(n) work inside loop =
// n*O(n) = O(n^2)
//This is quadratic run time.
void sort(double A[], int start, int end)
{
	for (int i = start; i <= end; i++) //#loops: n
	{
		int smallIndex = locateSmallest(A, i, end); //O(n)
		swap(A[i], A[smallIndex]);
	}
}

int main()
{
	//Quiz:  Write a locateSmallest function.
	double numbers[] = { 52, 17, 38, 58, 1238, 4, 13, 53, 12 ,85, 11, 388, 3, 0, 19 };

	//locate smallest should return the index
	//of the smallest number in the array
	//between the given range (inclusive)
	cout << locateSmallest(numbers, 0, 14) << endl; // 13
	cout << locateSmallest(numbers, 5, 8) << endl; // 5
	cout << endl;
	cout << endl;

	//Next:  can you sort the array?
	sort(numbers, 0, 14);
	printItems(numbers, 0, 14);

	return 0;
}