EECE 352: PS5

Problem 1 (50%): You will implement the myQuickSort function, which has the signature given below. The templated function you create should be able to sort objects of any type, as long as they have the appropiate operators and iterators defined for them.

You should use a cutoff of 5. At the cutoff you can either use the STL sort or, preferably, the insertion sort from PS3. The quicksort you will implement should be very similar to the one from Figure 8.20 in the book, except using iterators and the given signature.

Problem 2 (50%): A stable sort is one where elements that are equal are kept in the same order in the final list as they were in the original list. To illustrate I have created a class called Person which defines its own operator< and operator==. Two Persons are the same if they have the same name. If you were to apply your quicksort to the people vector provided in the main, you will notice that while they end up sorted based on name, the people with the same name (i.e. all the "joe"s) end up in a different order from the orginal.

You are to implement a function called myStableQuickSort (with the given signature), which can perform a stable sort on any vector of Persons. The way you do this is by creating a new vector that is the same as the vector of persons to be sorted but also includes the position of each Person. Then you make sure that if two Persons are equal (==) that they will be sorted based on the position. You might want to read Excercise 8.26 from the book since that is basically the same problem as this one. However note that solution he proposes is when using arrays, and not vectors.

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

using namespace std;


template <class Iter>
void myQuickSort(Iter low, Iter high){ //Implement this.
};

template <class Iter>
void myStableQuickSort(Iter low, Iter high){ //Implement this.
}


class Person { //You CANNOT CHANGE THIS CLASS, AT ALL, NONE, NADA.
	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);

        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;
}


The output of the above program should be:

9 2 4 5 7 3 8 1 10
1 2 3 4 5 7 8 9 10
bart - 5
homer - 5
joe - 1
joe - 1
joe - 2
joe - 2
joe - 4
joe - 4
lisa - 8
marge - 3
Press any key to continue