#include<iostream>
#include<algorithm>
#include<iterator>
#include<vector>
#include<string>

using namespace std;


template <class Iter>
void myQuickSort(Iter low, Iter high){ //Implement this.
//	cout << "Call=";
//	for_each(low,high, print);
//	cout << endl;
	if ((high-low) <= 5)
		sort(low,high);
	else {
		//sort low, middle, high
		Iter last(high -1); //because high points beyond last element
		int distanceToMid = (high -low ) /2;
		Iter mid = low + distanceToMid;
		if (*mid < *low)
			swap(*low, *mid);
		if (*last < *low)
			swap(*last, *low);
		if (*last < *mid)
			swap (*mid, *last);

		//move pivot to last position
		swap(*mid, *last);

//		for_each(low,high, print);
//		cout << "---";
		//begin partitioning
		Iter i(low);
		Iter j(last);
		for (;;){
			while(*(++i) < *last);
			while(*last < *(--j));
			if (i < j)
				swap(*i, *j);
			else
				break;
		}
		swap(*i, *last);//restore pivot
//		for_each(low,high, print);
//		cout << endl;
		myQuickSort(low, i); //i because the end is one beyond last element
		myQuickSort(i+1, high);
	}
};

template <class Any>
class Order {
public:
	int place;
	Any object;
	Order() : place(0) {}; //cant initialize object
	Order(int p, Any & o) : place(p), object(o) {};
	bool operator<(const Order & o) {
		if (object == o.object)
			return place < o.place;
		return object < o.object;}
	bool operator==(const Order & o) {
		return object == o.object;}
};
			

template <class Iter>
void myStableQuickSort(Iter low, Iter high){ //Implement this.
	vector<Order<Person> > v;
	//NOTE: The RIGHT way of doing this (which makes is work for ANY
	// class) is with:
	//typedef typename std::iterator_traits<Iter>::value_type elementType;
	//vector<Order<elementType> > v;
	// but this does not work in VC++ 6.0 since it does not support
	// partial template specialization. Maybe one of you can think of a way
	// to implement this so that it will work for any container.
	int j;
	Iter i(low);
	for (j =0; i != high; ++i, ++j){
		Order<Person> o(j,*i);
		v.push_back(o);
	};
	myQuickSort(v.begin(), v.end());

	//rewrite the old array with the new contents
	vector<Order<Person> >::iterator k;
	i = low;
	for (k = v.begin(); k != v.end(); ++k, ++i){
		*i = (*k).object;
	}
}


class Person { //You CANNOT CHANGE anything in this class.
	string name;
	int id;
public:
	Person() : name("") {};
	Person(const string & s, int i) : name(s), id(i) {};
	Person(const Person & p) : name(p.name), id(p.id) {}; //copy const.
	bool operator<(const Person & p) const{
		return name < p.name;};
	bool operator==(const Person & p) const{
		return name == p.name;};
	friend ostream & operator<<(ostream & os, const Person & p){
		os << p.name << " - " << p.id; return os;};
};

void print(int e){
        cout << e << ' ';
};

int main() {
        vector<int> v;
        v.push_back(9); v.push_back(2); v.push_back(4); 
        v.push_back(5); v.push_back(7); v.push_back(3);
        v.push_back(8); v.push_back(1); v.push_back(10);
		v.push_back(19); v.push_back(12); v.push_back(14); 
        v.push_back(15); v.push_back(17); v.push_back(13);
        v.push_back(18); v.push_back(11); v.push_back(110);

        for_each(v.begin(), v.end(), print);
        cout << endl;
		//Note that v.end() refers to one element BEYOND, the last one.
		//You should remember this when debugging your program.
        myQuickSort(v.begin(),v.end());
        for_each(v.begin(), v.end(), print); 
        cout << endl;

		vector<Person> people;
		Person p1("joe", 1); people.push_back(p1);
		Person p2("joe", 1); people.push_back(p2);
		Person p3("joe", 2); people.push_back(p3);
		Person p4("joe", 2); people.push_back(p4);
		Person p5("homer", 5); people.push_back(p5);
		Person p6("marge", 3); people.push_back(p6);
		Person p7("bart", 5); people.push_back(p7);
		Person p8("lisa", 8); people.push_back(p8);
		Person p9("joe", 4); people.push_back(p9);
		Person p10("joe", 4); people.push_back(p10);

		myStableQuickSort(people.begin(), people.end());
		vector<Person>::iterator it;
		for (it = people.begin(); it != people.end(); ++ it)
			cout << *it << endl;
        return 0;
}