//=============================================================================
// 215 Lab #8 Starter File
// Spring 2006
// STL Sort Algorithms


#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <time.h>

using namespace std;


//=============================================================================
// prototypes

void MakeRandomVectors( vector<int>&, vector<int>&, vector<int>& );
void TestIntroSort( vector<int>, vector<int>, vector<int> );
void TestMergeSort( vector<int>, vector<int>, vector<int> );
void TestHeapSort( vector<int>, vector<int>, vector<int> );

//=============================================================================
// main

int main()
{
	vector<int> randoms_a;    // each holds a sequence of random numbers
	vector<int> randoms_b;
	vector<int> randoms_c;

	// seed random number generator
	srand(time(NULL));

	// fill the three vectors
	cout << "Making Random numbers....";
	MakeRandomVectors( randoms_a, randoms_b, randoms_c );
	cout << "Done." << endl << endl;

	// sort each of the vectors in three different ways
	TestIntroSort( randoms_a, randoms_b, randoms_c );
	TestHeapSort( randoms_a, randoms_b, randoms_c );
	TestMergeSort( randoms_a, randoms_b, randoms_c );

	return 0;

} // end main





//=============================================================================
// TestIntroSort
//
// PRE:  Vectors randoms_a, randoms_b, and randoms_c have been initialized with
//       certain numbers of randomly generated integers.
// POST: Each vector is sorted via Introsort sorting method (introspective
//       sort, a variant of quicksort); the time for sorting each is reported
//       in seconds.

void TestIntroSort( vector<int> randoms_a, vector<int> randoms_b, vector<int> randoms_c )
{


} // end TestIntroSor





//=============================================================================
// TestHeapSort
//
// PRE:  Vectors randoms_a, randoms_b, and randoms_c have been initialized with
//       certain numbers of randomly generated integers.
// POST: Each vector is sorted via the Heapsort sorting method (first
//       reordering each vector as a heap, then sorting from the heap to a normal
//       sorted sequence); the time for sorting each is reported
//       in seconds.

void TestHeapSort( vector<int> randoms_a, vector<int> randoms_b, vector<int> randoms_c )
{


} // end TestHeapSort()





//=============================================================================
// TestMergeSort
//
// PRE:  Vectors randoms_a, randoms_b, and randoms_c have been initialized with
//       certain numbers of randomly generated integers.
// POST: Each vector is sorted via MergeSort; the time for sorting each is reported
//       in seconds.

void TestMergeSort(  vector<int> randoms_a, vector<int> randoms_b, vector<int> randoms_c )
{


} // end TestMergeSort




//=============================================================================
// MakeRandomVectors
//
// PRE:  The random number generator has been seeded.
// POST: The three vector parameters have been resized to different powers of
//       10 (10^6, 10^7, and 10^8) and filled with random numbers from 1 to
//       5000.

void MakeRandomVectors( vector<int>& randoms_a, vector<int>& randoms_b, 
					    vector<int>& randoms_c )
{
	int i;

	randoms_a.resize( pow( 10, 6 ) );
	randoms_b.resize( pow( 10, 7 ) );
	randoms_c.resize( pow( 10, 8 ) );

	for ( i=0; i<randoms_a.size(); i++ )
		randoms_a[i] = rand() % 5000 + 1;

	for ( i=0; i<randoms_b.size(); i++ )
		randoms_b[i] = rand() % 5000 + 1;

	for ( i=0; i<randoms_c.size(); i++ )
		randoms_c[i] = rand() % 5000 + 1;

} // end MadeRandomVectors