Homework 4

Details

We will begin to work on this assignment in class. To begin this assignment, do the following

1. Download and install MobaXterm (or find a similar program if you have an Apple).
2. Download the Sorting Project.
3. Unzip Sorting.zip. It will contain a single folder called Sorting.
4. Log into Loki (loki.cs.hope.edu) using your hope username and your student ID as password.
5. Copy the Sorting directory onto your account on Loki. This is as easy as drag-and-drop if you are using MobaXterm. If you have an Apple, that's your fault.
6. In the terminal, go to the command line and type "cd Sorting" to change directories to the Sorting directory.
7. Type "make" and enter to compile the project.
8. Type "./runSorts moderateSizedTests.txt 1234" to run the program.
9. Now improve quicksort2 and mergesort2 in the YourSorts.cpp file. You may add other methods to this file (and the declarations to YourSorts.h) and modify the existing methods, but do not change the method signatures of any existing methods! Also, do not change any of the other code!

Work in pairs to finish optimizing both Quicksort or Mergesort. Do not simply split the assignment so that each person works on one algorithm. You will do much better if both of you work together on both algorithms.

Grades for this assignment will be based mainly on performance improvements compared to the original algorithms. I will also compare your performance with that of qsort, your classmates, and (if I get around to it) my best algorithms. I will run tests similar to those in fullRangeTests.txt, but my tests may be slightly different.

To get an 'A', you want to be the fastest algorithm. To get a 'B', you want to have made significant improvements and it should be obvious that you put effort into the improvements. For instance, your attempts should not be limited to changing just 2 or 3 lines of code and/or implementing just one improvement. If you only made minor changes/improvements, and it appears you did not try very hard, you will get a 'D' or worse.

Quicksort will be much easier to improve than Mergesort. However, there is an improvement that can make Mergsort about twice as fast by reducing the number of times arrays are copied. It turns out that the amount of code that needs to be added/changed is very small, but it is pretty tricky getting it just right!

Make sure both names are at the top of the YourSorts.cpp file, zip up the Sorting directory and have one person submit it using Webhandin 385-HW4.