In this lab, you will use a stack to replace recursion. The idea is to use the stack to hold "tasks" that are waiting to be performed. (This is similar to the blobCount() example that we did in class and is not covered in the textbook.) The algorithm that you will work on is QuickSort. The goal of the lab is to produce a version of QuickSort that runs as quickly as possible. In addition to substituting a stack for recursion, there are a few other tricks that you can try.
To begin the lab, you can create a new Eclipse project and copy the files from the folder /classes/f07/cs225/files_for_lab_7 into that project. The files include a main program, QuickSortDemo.java that includes a QuickSort implementation, and a file StackOfInts.java that implements the StackOfInts Abstract Data Type.
Because of Fall Break, the due date for this lab (Lab 7) will be Thursday, October 18. Your work should be in your CVS repository by 3:00 PM on that day. I will have office hours on that day, starting at 10:00 AM.
Lab 6 is due, but I will not check your work until the morning of Wednesday, October 10. Before then, you should make sure that your project for Lab 6 is checked into your CVS repository and is up-to-date.
As it is usually implemented, QuickSort is a recursive algorithm, but as we have seen in class, it's always possible to eliminate recursion from an algorithm and use a stack instead. Your task is to do this for QuickSort and then to do some tests on the run times of the two versions.
You should write a new QuickSort method, using a stack instead of recursion. Add your method to the file QuickSortDemo.java. Your method can call the quicksortStep method that is already defined in that file. You will be imitating the sort of thing that we did with the non-recursive version of blobCount() in class. For a stack, it can use the StackOfInts class that is defined in StackOfInts.java. Make sure that your non-recursive QuickSort method is working before you proceed with the rest of the lab!
Since calling a method involves more overhead than pushing and popping from a stack, the non-recursive version of QuickSort should be faster than the recursive version. Test this by creating a large array and making a copy of that array. Then sort the array using both the recursive and the non-recursive versions of QuickSort. Measure the run time in each case, and compare the run times. Keep track of your results so that you can report on them. (The last time that I actually tried this, the difference was only about 15%, which I thought was disappointingly small. I don't know exactly what to expect this time around.)
You might also want to check your time against the built-in sort method, Arrays.sort(A), where Arrays is a standard class in package java.util.
Whatever your results, see if you can improve the performance of your non-recursive QuickSort. You might want to keep several versions of the algorithm in your project, so that they are available for grading, even if they are not used in your fastest implementation. For this part of the lab, you are not required to implement every technique that is suggested below, but the fastest version of QuickSort will be worth some extra credit to the person who programs it.
In your QuickSort implementation, try not to use the stack more than necessary. When you apply QuickSortStep, it divides a task in two sub-tasks. Only one of those sub-tasks needs to go on the stack; the other one you can work on directly, by adjusting the values of hi and lo directly instead of putting them on the stack. Sometimes a sub-task produced by QuickSortStep is trivial -- that is, the sub-task is to sort a list of length zero or one. In that case, there is nothing to do and the sub-task can be discarded entirely. You only need to go back to the stack for a new task when both of the sub-tasks produced by QuickSortStep are trivial.
Another idea is to consider the size of the stack. Growing the stack takes a certain amount of time. You can minimize the maximum size of the stack as follows: When QuickSortStep produces two sub-tasks, place the larger of the two sub-tasks on the stack, and work on the smaller sub-task first. (Here, the size of the task just means the length of the sequence that is to be sorted.) By working on the smaller sub-task first, you guarantee that the stack will never grow larger than log2(n), where is is the size of the entire array. If you don't follow this policy, then the size of the stack can conceivably grow as large as n2. (Note: Although we have talked only about time efficiency of algorithms, space efficiency can also be an important issue. Space efficiency refers to the amount of memory used by the algorithm. QuickSort is one of the algorithms where an analysis of space efficiency is interesting.)
A final idea is to try to optimize your method even more by applying the following suggestion. As you might have observed in Lab 3, Insertion Sort can actually be faster than QuickSort on a very small array. This means that you might be able to make QuickSort faster by switching to Insertion Sort when the size of the list that you are sorting is small. The best cut-off value for the task size can be determined empirically by testing various possible values. (I suspect that the best cutoff is very small, on the order of 3, 4, or 5, but I have not tested this.) Alternative, you might try using some simple direct method of arranging two or three elements in order. For example, for a two-element sequence, you can simply compare the two items and swap them if necessary.
You should write a report on the run times that you get for various QuickSort implementations. Place the report in a separate text file in your Eclipse project.