#include <iostream>
#include <cstdlib>
#include <fstream>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

unsigned long comp = 0;

const int median3(vector<int> &a, int left, int right)
{
	int center = (left + right)/2;	//get middle index

	// Put three element in order
	if(((a[left] < a[center])&&(a[center] < a[right])) || ((a[right] < a[center])&&(a[center] < a[left])))
		return center;
	else if(((a[center] < a[left])&&(a[left] < a[right])) || ((a[right] < a[left])&&(a[left] < a[center])))
		return left;
	else
		return right;
}

void qsort(vector<int> &a, int left, int right)
{
	//int pivot = a[left];	//choose 1st element as pivot

	//int pivot = a[right - 1];	//choose last element as pivot
	//swap(a[left], a[right - 1]);

	int median_of_three = median3(a, left, right - 1);
	//choose median element as pivot
	int pivot = a[median_of_three];
	swap(a[left], a[median_of_three]);

	int begin = left, end = right;

	int i = begin + 1, j = begin + 1;

	if((begin + 1) == end)
		return;

	for(; j < end; j++)
	{
		if(a[j] < pivot)
		{
			swap(a[i], a[j]);
			i++;
		}
	}
	swap(a[begin], a[i-1]);

	comp += end - (begin + 1);

	//test the value of i
	//cout << "i = " << i << endl;
	if(i > (begin + 1))
		qsort(a, begin, i-1);
	if(i < end)
		qsort(a, i, end);
}

int main(void)
{
	const clock_t begin_time = clock();	// begin time
	ifstream myfile;

	myfile.open("QuickSort.txt");
	if(!myfile)
	{
		cerr << "Cannot open file!\n";
		exit(1);
	}

	//test comp
	cout << "Comp = " << comp << endl;
	// Read data
	vector<int> Input;
	string temp;

	while(!myfile.eof())
	{
		getline(myfile, temp);
		if(temp.size() == 0)
		{
			continue;
		}
		Input.push_back(atoi(temp.c_str()));
	}

	myfile.close();


	//cout << double(begin_time) << endl;

	int length = Input.size();
	cout<<length<<" numbers acquired.\n";

	// Quick sort for input array
	qsort(Input, 0, length);
	cout << "Time:(ms) " << double(clock() - begin_time) / CLOCKS_PER_SEC * 1000.0 << endl;
	//cout << "1st: " << Input[0] << endl;
	cout << "Comp = " << comp << endl;

	//test
	vector<int> mytest;
	mytest.push_back(3);
	mytest.push_back(1);
	mytest.push_back(2);

	//qsort(mytest, 0, 3);
	//cout << "After: " << mytest[0] << endl;
	//cout << "Comp = " << comp << endl;

	return 0;
}