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

class ads_item
{
	int data;
public:
	// Counters for assignments and comparisons
	static size_t assignments_count, comparisons_count;
	
	// Constructor. Initialize items with random values.
	ads_item() 
	{
		data = rand();
	};
	
	// Constructor with copying.
	ads_item(const ads_item & other) : data(other.data)
	{
		++assignments_count;
	};
	
	// Reset counters to 0.
	static void reset()
	{
		assignments_count = 0;
		comparisons_count = 0;
	}
	
	// Overloading comparison operation.
	bool operator<(const ads_item &other) const
	{
		++comparisons_count;
		return data<other.data;
	}
	
	// Overloading assignment operator.
	const ads_item &operator=(const ads_item &other)
	{
		++assignments_count;
		data = other.data;
		return *this;
	}
	
	// Declare output operation as a friend.
	friend std::ostream & operator<<(std::ostream & out, const ads_item & item);
};

// Initializing static members
size_t ads_item::assignments_count = 0;
size_t ads_item::comparisons_count = 0;

// Overloading output operation as a friend.
std::ostream & operator<<(std::ostream & out, const ads_item & item)
{
	return out << item.data;
}

// Quick sort for vector data type. Using std library algorithm.
void quicksort(std::vector<ads_item> & vect)
{
	sort(vect.begin(), vect.end());
}

// Stable sort for vector data type. Using std library algorithm.
void stablesort(std::vector<ads_item> & vect)
{
	stable_sort(vect.begin(), vect.end());
}

using namespace std;

int main(int argc, char* argv[])
{
	
	// One argument needed (length of the array to be sorted).
    if (argc != 2) 
	{
        cout << "Invalid number of arguments: " << argc-1 << " instead of 1." << endl;
		cout << "Please specify the length of the array to be sorted." << endl;
        return 1;
	}

	// argv[0] = program file name
    int array_len = atoi(argv[1]);
	
	// Initialize random number generator.
	srand(static_cast<unsigned int>(time(NULL)));
	
	// Define identical vectors of the specified length.
	vector<ads_item> v_quick(array_len), v_stable(v_quick);

	// Display info about operations counts.
	cout << "Vectors created : " << array_len << " items\n";
	cout << "Assignments : " << ads_item::assignments_count << " comparisons : ";
	cout << ads_item::comparisons_count << endl;

	// Run quicksort.
	ads_item::reset();
	quicksort(v_quick);
	cout << "\nQuick sort: assignments : " << ads_item::assignments_count;
	cout << " comparisons : " << ads_item::comparisons_count << endl;
	
	// Run stablesort
	ads_item::reset();
	stablesort(v_stable);
	cout << "\nStable sort: assignments : " << ads_item::assignments_count;
	cout << " comparisons : " << ads_item::comparisons_count << endl;

//	system("PAUSE");
	return 0;

}