25 points; due Mon 4/28 @ 11am.
This assignment may optionally be done with a partner.
In this assignment, most of the code is provided for you. You will just have to fill in one method, the one that does Shell sort. Your task is then to run some experiments, investigate your results, and write up a report of what you found.
Download Sorter.java and take some time to study it. It's a big program, but it has basically four components:
- Implementations of a bunch of sorting algorithms (with Shell sort left blank).
- A bunch of code for interpreting command-line arguments.
- A method for generating an array of random integers.
- A couple timing commands wrapped around the call to the sorting algorithm of choice.
For a given value $n$, we can generate an array of $n$ unique integers in random order, and then sort it with a chosen sorting algorithm. The question at hand is this: what's the relationship between $n$ and the running time, for each different algorithm? How do the algorithms compare to each other? What predictions can we make about really huge values of $n$?
One way to investigate this question is by timing the algorithms for various values of $n$, and making graphs of the timing results. That's what you'll do for this assignment.
What to hand in
Hand in via Moodle:
- A report describing the timing experiments you performed, your timing data, and your interpretation of what your results say about the relationship between $n$, the algorithm, and running time. Your report should be a PDF file no longer than 3 pages including charts and graphs, if any. (Note that no format other than PDF is acceptable. That means no .docx, no RTF, no .txt, none of that. You must hand in a PDF.)
- Source code you used to collect your timing data (including your implementation of Shell sort).
You will be graded on the depth of your investigation and the clarity of your writeup. Try to figure out if there's an explanation for the results you see. You have an assigned reading this weekend, Chapter 4 (actually just 4.1—22), which defines a mathematical language for talking about performance figures like this.
Specifically, please address the following questions:
- Does selection sort act like a $\Theta(n^2)$ algorithm? How can you tell?
- Does insertion sort act like an $O(n^2)$ algorithm? How can you tell?
- Insertion sort's best-case performance is $\Theta(n)$. Can you see this in real-life timing?
- Does mergesort act like a $\Theta(n \log(n))$ algorithm? How can you tell?
- Overall, how does selection sort perform in comparison to insertion sort?
- Overall, how does mergesort perform in comparison to shellsort?
- Which of these algorithms would be the best choice for a really huge $n$?
Suggestions and offerings
- There's nothing mysterious about this assignment. We want to understand the relationships, if any, between $n$, the choice of algorithm, and running time. Your job is to use your excellent experimental and analytical abilities to discover what you can about those relationships.
- You may change the code however you please, but make sure you don't interfere with the logic of the sorting algorithms!
- In order to investigate why the algorithms have the kind of performance they do, you might want to count things like comparisons, variable assignments, and function calls during the execution of the algorithm. The easiest way to do this would be to add some static member variables to the class.
- If you make changes to the code beyond implementing Shell sort, make certain that your timing code is wrapping only the sorting algorithm (and possibly your bookkeeping code for counting particular types of operations). Do not print out debug output during a sort if you're timing it as part of your report; printing output takes a bizarrely long time, and it will totally throw off your results.
- Sure, you could work alone. But it's pretty cool when you say “I wonder what happens if we do this?” and your partner says “Let's try it!”
Create a zip file called hw8.zip containing your writeup (which must be a PDF file, no exceptions!) and your Sorter.java file. Submit the zip file on Moodle.
Start early, ask lots of questions, and have fun!
Grading
- Shell sort implementation — 5 points
- Thoroughness of investigation — 10 points
- Clarity of writeup — 10 points