CS35 Lab 6: Sorting

Due by 3:14:08 a.m., Tuesday, January 19, 2038

Like lab 00, you will not hand in this lab. You may work with partners as you desire. As usual, though, run update35 to get the initial files for this lab.

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.


Completing quickSort and partition
You should complete the implementation of two templated functions in quicksort.inl:

To complete this work you do not need to edit any files except for quicksort.inl, and you only need to modify quicksort.inl in the locations marked with "TODO". Once you are done, you can test your work using the provided testQuickSort program, which uses quick sort to lexicographically sort an array of Points by their x- and y-coordinates.

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



Implementing comparison functions for the Person class

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.cc for our implementation, and testPoint and testQuickSort for testing purposes.

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.cc implementation file, you should be able to sort an array of people using the testPerson program.



Do not submit

Do not submit your work for this lab.