CS 2420: Introduction to Computer Science II: Homework 5

CS 2420:
Introduction to Computer Science II
Homework 5

Assigned: Friday, Sep 26, 2014
Due: Monday, Oct 20, 2014, at 3pm.

Homework 5

Part I: Implement Five Sorts

Implement the five sorts we discussed in class: BubbleSort, SelectionSort, InsertionSort, MergeSort, and QuickSort. For QuickSort implement three pivot selection strategies: last element, random element, median-of-three (first, middle, and last). The implementation should use java generics to sort lists containing any sort of Comparable object.

Part II: Run Timing Experiments

Run all 5 sorts on sorted, reverse sorted, and random inputs of different sizes (10, 100, 1000, 10000, 100000, 1000000). For small inputs, you should run the experiment many times and divide the timing results by the number of iterations (i.e. compute the time required to sort 1000 random lists of size 10, then divide by 1000). Plot the results. This should result in 21 curves (Bubble, Selection, Insertion, Merge, and three Quick) x (sorted, reverse sorted, and random). Draw some conclusions from your results.

What to hand in

Create a web page for the assignment. Add your graphs and the conclusions you've drawn. Use the CADE online handin system to handin your source code. Please zip and handin your entire project directory (including an info.txt file). If you work in a team only one of you need to submit the source code, but both need to make web pages.

Grading

Each homework assignment will receive a grade out of 100 points. This week, the available points will be broken down like so:

50 points: Sort Implementation
20 points: Graphs and conclusions
10 points: Comments describing the class, each method as well as the interesting pieces of the code itself
10 points: Elegence of programming
10 points: Picture and web page