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


void displayArray(double * items, int start, int end)
{
	for (int i = start; i <= end; i++)
		cout << items[i] << " ";
	cout << endl;
}



//The legendary "Blaze Sort" algorithm.
//Sorts the specified portion of the array between index start and end (inclusive)
//Hmmm... how fast is it?
/*
void blazeSort(double * items, int start, int end)
{
	if (end - start > 0)
	{
		int p = filter(items, start, end);
		blazeSort(items, start, p - 1);
		blazeSort(items, p + 1, end);
	}
}
*/

int main()
{
	////////////////////////////////////////////////////
	//Part 1:  Implement a method called filter.
	////////////////////////////////////////////////////

	//Filter is a function that takes in an array and a range (start and end).
	//
	//Call the first item in the range the 'pivot'.
	//
	//Filter's job is to simply separate items within the range based on whether they are bigger or smaller than the pivot.
	//In the example array below, 13 is the pivot, so all items smaller than 13 are placed in indices 0-3.  The pivot is then placed at index 4, and all
	//remaining items, which are larger than the pivot, are placed at positions 5-10.  Note that the array is NOT sorted, just "partitioned" around
	//the pivot value.  After doing this, the function must return the new index of the pivot value.

	double testNumsA[] = { 13, 34.1, 43, 189, 4, 4.5, 18.35, 85, 3, 37.2, 5 };

	//The filter will place all items <= 13 to the left of value 13, and all items large than 13 to the right of 13 in the array.
	int p = filter(testNumsA, 0, 10);
	cout << p << endl; //should be 4, the new index of 13.
	displayArray(testNumsA, 0, 10);  //should display something like this:  5 3 4.5 4 13 18.35 85 189 37.2 43 34.1

	//One more example:
	double testNumsB[] = { 13, 34.1, 43, 189, 4, 4.5, 18.35, 85, 3, 37.2, 5 };
	p = filter(testNumsB, 2, 6);  //Here we are only interested in items from indices 2-6, ie, 43, 189, 4, 4.5, 18.35
	cout << p << endl; //should be 5
	displayArray(testNumsB, 0, 10); //Notice only indices 2-6 have been partioned:  13 34.1 18.35 4 4.5 43 189 85 3 37.2 5


	/////////////////////////////////////////////////////////////////////////////////
	//Part 2:  Uncomment "Blaze Sort".
	//Blaze Sort uses/needs your filter to work properly.
	/////////////////////////////////////////////////////////////////////////////////


	//Test if Blaze Sort correctly sorts the following array.
	double testNums[] = { 13, 34.1, 43, 189, 4, 4.5, 18.35, 85, 3, 37.2, 5 };

	blazeSort(testNums, 0, 10);

	displayArray(testNums, 0, 10);

	/////////////////////////////////////////////////////////////////////
	//Part 3:  Test how fast Blaze Sort is for large arrays.
	//What do you think the run-time (big-Oh) of blaze sort is?
	/////////////////////////////////////////////////////////////////////

	//Stress test:
	int size = 100; //test with: 1000, 10000, 100000,1000000, 10000000
	double * numbers = new double[size];

	for (int i = 0; i < size; i++)
	{
		numbers[i] = rand();
	}

	clock_t startTime, endTime;

	startTime = clock();
	blazeSort(numbers, 0, size - 1);
	endTime = clock();

	displayArray(numbers, 0, size - 1);
	cout << "Blaze sort took: " << endTime - startTime << " milliseconds to sort " << size << " doubles."  << endl;

	////////////////////////////////////////////////////////////////////
	//Part 4: Sort Moby Dick, but this time with Blaze Sort
	///////////////////////////////////////////////////////////////////

	//////////////////////////////////////////////////////////////////
	//1) Create a second version of Blaze Sort that sorts arrays of strings
	//(instead of arrays of doubles).
	//2) Download whale.txt from the previous lab.  Read the words from the file into
	//an array, sort the array with Blaze Sort, and then write the sorted words to an output file.
	//
	//This time, it has to be fast!  Must finish in under 10 seconds.
	/////////////////////////////////////////////////////////////////

	return 0;
}