A skeleton version of the programs will appear in your cs35/lab/06 directory when you run update35. The program handin35 will only submit files in this directory.

You may work with a partner on this lab

The quicksort routine we wrote in class works fine as long as we just want to sort an array of integers. However, many complex objects have a natural order that we can use to sort e.g., sorting strings alphabetically, sorting cards by rank, sports teams by number of wins. In this lab, you will use templates and a comparison functions to create a more generic sort. Before diving into to the main part of the lab, modify quicksort to support random pivoting. This process is a short modification to the current partition function as outlined below:

pick a random index k between left and right inclusive. 
swap(array, k, right);
proceed as normal

We will be templating the quicksort code. Because templating in C++ is handled by the preprocessor, we cannot have a quickSort.cpp file. Start by migrating quickSort.cpp to quickSort.inl by following these steps:

1. mv quickSort.cpp quickSort.inl
2. edit the Makefile to remove references quickSort.cpp and quickSort.o The new makefile should only include

   #TODO add support for your class
   
   all: testQuick
   
   testQuick: randarray.o randarray.inl quickSort.inl testQuick.cpp
   	g++ -g -o testQuick randarray.o testQuick.cpp
   
   randarray.o: randarray.h randarray.cpp
   	g++ -g -c randarray.cpp 
   
   clean:
   	rm *.o testQuick
   
   .PHONY: clean all
   

3. add the appropriate #ifndef, #define, #endif to quickSort.inl. Use quickSort.h for an example
4. add the line #include "quickSort.inl" to the end of quickSort.h (but before the #endif in quickSort.h)

Check that your code still compiles at this point and make adjustments as needed before proceeding. Template partition, swap, and quickSort in both quickSort.h and quickSort.inl, by adding the line template <typename ITEM> in front of each function declaration/definition. Change the int type to ITEM type in the appropriate locations. Note you should only change int type to ITEM when refering to an actual element of an array. Sizes, and relative positions within the array should still be integers. You will only need to change about five locations in quickSort.inl

After making changes, test your code. You should not need to change testQuick.cpp at all. If the integer array test works, uncomment the sections in main() to test the floating point number code. If you templated on ITEM type properly, both the integer and floating point versions should work fine.

The code you have now allows users to sort any object that has a < operator defined. It will always insert in increasing order based on the definitin of <. In some applications we may want to sort the same type of data multiple ways (ascending, descending, by age, by name, etc.). In this step, we will generalize our sort not only on ITEM type, but also the means to compare two elements.

Here is the basic idea. Suppose we have a function compare that takes as input two paremeters a and b of the same type, and returns a Boolean value. The function returns true if a should come before b in sorted order, otherwise the function returns false. We could view compare(a,b) as being similar to a < b, but now we can choose different ways to compare.

To implement this in C++, we will template quickSort and partition to take a second template argument CMP, for example. The variable cmp will be our comparision function.

template <typename ITEM, typename CMP>
int partition(ITEM array[], int left, int right, CMP cmp);

Now, instead of using the < symbol to compare two elements in the array, rewrite partition to use cmp(a,b). Note cmp(a,b) returning true means that a should come before b in sorted order. Note you cannot use ==, < , <=, >, or >= when comparing elements directly. You should only use cmp and figure out how to say >=, or == using cmp.

After modifying your code to contain two template arguments, you will need to modify your testQuick.cpp file since quickSort now takes four arguments. First try the following. Modify your call to quickSort in main such that the fourth and final argument to quickSort is less<int>(). This standard snippet of code available in #include <algorithm> creates a comparison function equivalent to < . In essence, it looks like this

template <typename T>
bool less(ITEM first, ITEM second){
  return first < second;
} 

Next try writing your own function is_greater in testQuick.cpp that takes two integers as input and return true if the first integer is greater than the second. Replace less<int>(), with is_greater (no parentheses). Quicksort should now sort the list in decreasing order since items that are greater should come before smaller items.

At this point, you have a generic sort that can sort any type of data in any way given a comparision function.

Experiment with your new sort by creating a class of your own (create separate .h and .cpp files) and writing a Boolean function that compares two items in your class. Create an array of your new objects, sort them using your comparision function and display the results. Some example classes might include:

• A Point3D class with x,y,and z coordinates. You can write different comparision functions in testQuick.cpp that compare two Point3D objects by x, y, or z coordinate.
• A SportsTeam class that has a name, number of wins, and number of losses. You can sort by name, number of wins, or winning percentage.
• Something of your own choosing.

It will probably be helpful to have a print() method in the class you create so that you can easily display all your objects before and after sorting. When testing on these arrays of objects, you do not need to sort large lists. Five or six elements should suffice. You just need to observe that quickSort arranges elements in the proper order.

You will need to modify your Makefile when adding a new class. Below is an example that adds a thing class. You need to tell make to build thing.o and that testQuick now depends on thing.o

testQuick: testQuick.cpp thing.o
	g++ -o testQuick thing.o testQuick.cpp

thing.o: thing.cpp
	g++ -c thing.cpp -o thing.o

clean:
	rm *.o testQuick

Once you are satisfied with your code, hand it in by typing handin35. This will copy the code from your cs35/lab/06 to my grading directory. You may run handin35 as many times as you like, and only the most recent submission will be recorded. If you worked with a partner, only one of you needs to handin the code.

Home Page

Last updated: Tuesday, September 22, 2020 at 01:07:42 PM