Lab 7: QuickerSort? (With Stacks!)

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
*log*_{2}(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 n^{2}. (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.