CS 206 - Introduction to Data Structures
HW 8
Sorting
Assigned: Nov 13
Due: ????
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 one of those methods and test how much faster it is that basic quicksort.
Tasks (probably best done in this order):
-
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.
- Write a recursive implementation of Quicksort that is consistent with the pseudocode presented in class.
- Time your algorithm for sorting arrays of 1000 up to about 20 million items. If your computer bogs down on 20 million then stop early. Increment sizes by a factor of 4. (1000, 4000, 16000, 64000, ...). Because you are dealling with randomness, at each step, record the average over at least 5 trials (and preferably more than 20).
- Adapt your quicksort algorithm to stop recurring whenthe size of the portion of the array being recurred upon falls below some number N. (N should be easily changed in your program.) As a start, try N=20. Pass the resulting partially sorted array to an implementation of insertion sort. (Your implementation of insertion sort should mirror the iterative algorithm described in class.) This algorithm is often called Hybrid Quicksort (because it is a hybrid of insertion sort and quicksort).
- 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%.
- In your readme file include a table of you timing runs for standard and hybrid quicksort.
- In your readme file include a paragraph (or 2) explaining why hybrid quicksort is usually faster than quicksort (even if your data suggests no difference). You should also discuss why the time for Hybrid does NOT grow by O(N^2>)
- Extra Credit: determine an optimal value of N for your implementation and computer based on times for sorting 1 million or more items. To do so, you might use a binary search inspired algorithm. If you have written your code well, then this extra credit will take some time as you will need to run a bunch of tests, but it should not take much (if any) new code. Note that you are unlikely to get a single optimal value. Rather you should expect a range over which the results are nearly the same.
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.
- README: This file should follow the format of this sample README (https://cs.brynmawr.edu/cs206/README.txt)
- Source files: Every .java file used in the final version of every part of your project (including the imported files)
- Unique Data files used: This is expected to be blank as the only data files you should use are as above. However, you could use a data file (or two) as a part of your test driver class (I do not recommend this, I simply note that you could).
DO NOT INCLUDE: Data files that are read from the class site.
The following steps for submission assume you created a folder named AssignmentN in the directory /home/YOU/cs206/ and that folder contains all of your code.
- For this assignment N=8
- Put the README file into the project directory (/home/YOU/cs206/AssignmentN)
- In the README, include all of the data requested above for Jen and Jill and a brief discussion of the data (answering at least the two posed questions).
- Go to the directory /home/YOU/cs206
- Enter submit -c 206 -p N -d AssignmentN
For more on using the submit script click here