For this lab, you will work individually and submit your own solution. As usual, though, run update35 to get the initial files for this lab. This is an abbreviated lab, and will not be graded except to verify you completed the assignment.

This lab consists of two parts:

1. Complete a templated implementation of quickSort and its helper function, partition.
2. Augment the Person class with comparison operators.

You should complete the implementation of two templated functions in quicksort.inl:

• void quickSort(T a[], int left, int right): Uses quick sort to sort a range (inclusive) within an array.
• int partition(T a[], int left, int right): Partitions a range in an array around a randomly-chosen pivot element. It first swaps a random element to the rightmost position in the range, and then partitions the range as described in lecture. This function must return the final position of the pivot element in the partitioned array.

To complete this work, you mainly only need to implement quicksort.inl, modifying only in the locations marked with TODO. Once you are done, you can test your work using the provided testQuickSort program which sorts an array of ints.

For your reference, the algorithms described in lecture were:

    quickSort(a, left, right):
        if (left < right):
            p = partition(a, left, right)
            quicksort(a, left, p-1)
            quicksort(a, p+1, right)


    partition(a, left, right):
        l = left
        r = right-1
        pivot = a[right]

        while (l <= r):
            if (a[l] <= pivot):
                l++
            else if (a[r] > pivot):
                r--
            else:
                swap(a, l, r)

        swap(a, l, right)
        return l

In C++, each class may implement its own comparison operators <   <=   >   >=   != and == to define how items of that class are compared. This is convenient because it allows generic algorithms, such as our templated quick sort algorithm, to compare items of arbitrary classes using the built-in comparison symbols.

As an example, we've augmented our earlier Point class (from week 2!) with (somewhat simpler than normal) comparison operators. Our implementation compares two Points by first comparing their x-coordinates (returning that a point p1 is less than a point p2 if p1.x < p2.x) and then breaking ties by comparing their y-coordinates. We've also demonstrated a second possible comparison function which compares two points by comparing their distance from the origin (0,0). See point.h and point.cpp for our implementation, and testPoint and testQuickSort for testing purposes. In testQuickSort, once you get it working for integers, comment out the block at the bottom which uses quick sort to lexicographically sort an array of Points by their x- and y-coordinates.

Your task is to augment the Person class with comparison operators, comparing two Persons using whatever criteria you want. Once you have added the necessary operators to the person.h header file and person.cpp implementation file, you should be able to sort an array of people using the testPerson program. Be sure to indicate your criteria in the header comments of your function so it's obvious to a user of your class how you rank Person objects.

Run handin35 to submit your program. Be sure to complete both parts of your program.

Home Page