CS 206 - Introduction to Data Structures

Quicksort

Quicksort is undoubtedly quick. It is generally regarded as the fastest sorting algorithm. Over the years there have been many approaches to making quicksort even faster. In this homework you will implement quicksort and one of the methods for improving the speed of quicksort. Then you will test how much faster the improved version is than basic quicksort.

Tasks (probably best done in this order):
  1. Copy from /home/gtowell/Public/206/a8 the following code: SortBase.java and Selection.java. Selection.java implements selection sort. It is included only as an example of the use of the SortBase class. Mostly what SortBase gives you is a function for generating a randomized list of integers.
  2. Write a recursive implementation of Quicksort that is consistent with the pseudocode presented in class. (Note that your implementation need only be recursive at the "top level". That is, the split function can use loops.)
  3. Time your algorithm for sorting arrays of 10,000 up to 10,240,000 items. If your computer bogs down on 10 million then stop early. Increment sizes by a factor of 4. (1000, 4000, 16000, 64000, ...). Because you are dealing with randomness, at each step, record the average over at least 5 trials (and preferably more than 20). (Suggestion, use a spreadsheet to record your data.)
  4. Adapt your quicksort algorithm to stop recurring when the size of the portion of the array being recurred upon falls below some number N. (N should be easily changed in your program. This might be an excellent opportunition to use a private static final variable. Yes, I am actually recommending using a static.) As a start, try N=30. Pass the resulting partially sorted array to an implementation of insertion sort. Importantly your insertion sort should only sort the portion of the array it was passed, not the whole thing. You may use iteration in you insertion sort. You may copy the insertion sort code from page 293 of the textbook or adapt the psuedocode from the lecture note on April 23. If you copy the code from the text, the function should NOT be static, it should take an array of integers (rather than a list) and it should work on a portion of the array rather than the entire array.

    This algorithm is often called Hybrid Quicksort (because it is a hybrid of insertion sort and quicksort).
  5. Collect times for your Hybrid Quicksort that exactly mirror those you collected for standard quicksort. Your times should be slightly faster for hybrid than for standard. Your times for hybrid should certainly NOT grow according to O(N^2) that you might expect from insertion sort. You may only see a difference at the largest sort sizes. For my implementation, the speedup is about 10%. Some of you may have a slightly negative improvement.
  6. In your readme file include a table of you timing runs for standard and hybrid quicksort.
  7. In your readme file include a paragraph explaining why hybrid quicksort is usually faster than quicksort (even if your data suggests no difference). For inspiration, you might look in the textbook (in section 12.2.2) You should also discuss why the time for Hybrid does NOT grow by O(N^2)

Electronic Submissions

Your program will be graded based on how it runs on the department’s Linux server, not how it runs on your computer. The submission should include the following items:

The following steps for submission assume that you created a project named AssignmentN in the directory /home/YOU/cs206/

  1. For this assignment N=8
  2. Put the README file into the project directory
  3. Go to the directory /home/YOU/cs206
  4. Enter /home/gtowell/bin/submit -c 206 -p N -d AssignmentN

For more on using the submit script click here