Bill Manaris : Spring 2016 / CSCI 230 Homework 5

Assigned Date: Thursday, Apr. 14, 2016
Due Date: Wednesday, Apr. 27, 2016
Due Time: Section 2 at 8:25am / Section 1 at 11:15am

Last modified on April 25, 2016, at 08:23 PM (see updates)

Purpose

This assignment focuses on:

This is a solo assignment. You may discuss the assignment only with the TA or the instructor.

Learning Outcomes

Assignment

Create a Java program, compareSorts.java, which implements insertion sort, mergesort, and quicksort.

Run several comparisons of the above algorithms, as implemented, and collect your findings. While doing that,

Write a short report summarizing your findings.

Code

Your program should have the following sorting methods (as provided in class):

  1. public static void insertionSort(int [] a)
  2. public static void mergesort(int [] a), which calls:
    • private static void mergesort(int [] a, int [] temp, int left, int right), which recursively sorts list a.
  3. public static void quicksort(int [] a), which calls:
    • private static void quicksort(int [] a, int left, int right), which recursively sorts list a.
    • Additional helper methods include:
      • private static int getPivot(int [] a, int left, int right), which returns the index of the median of three values (left, center, and middle)
      • private static void swap(int [] a, int i, int j), which swaps values at the two indices i and j.

Input

The program should accept several lines of input, as follows:

The first line contains an int (e.g., 1), which specifies which method to run (e.g., the first method above).

The second line contains an int (e.g., 6), which specifies the size of the list to read in.

The third line contains a list of ints, whose length was given in the previous line (e.g., the list contains 6 ints).

You may assume that the input is formatted properly and is valid.

Output

On the first output line, your program should output the original list (all in one line).

On the second line, it should output the sorted list (again, in one line).

The third line should consist of this message "Sorting by method took x milliseconds...", where method is the name of the method (e.g., "mergesort"), and x is a double number.

Hint: To time your code you may use the following:

long startTime = System.nanoTime();   // start timing

methodToTime();

long endTime = System.nanoTime();    // end timing
double runtimeInMilliseconds = (double)(endTime - startTime) / 1000000.0;
 

I/O Sample 1

For example, given this input:

2
6
24 7 54 50 22 20
 

the output of your program should be (of course, the timing may differ):

24 7 54 50 22 20
7 20 22 24 50 54
Sorting by mergesort took 0.01 milliseconds...
 

I/O Sample 2

For example, given this input:

-2
10
 

the output of your program should be something like this (the actual numbers will most likely be different, as they are randomly generated to be sorted - also, the timing may differ):

809 619 419 389 620 197 804 597 722 889
197 389 419 597 619 620 722 804 809 889
Sorting by mergesort took 0.013 milliseconds...
 

Documentation

Follow the Golden Rule of Style: "A program should be as easy for a human being to read and understand as it is for a computer to execute." [1]

In general, you should comment any variable, obscure statement, block of code, method, and class you create.

Your comments should express why something is being done, as opposed to how the how is shown by the code.

Also see the course documentation standards in homework #1.

NOTE: You may use Javadoc formatting, if you prefer. If so, do it consistently.

Report

The report should be formatted using the ACM Proceedings format.

Provide a meaningful title, e.g., "Comparison of ... Employing Random Data"

It should consist of the following sections:

Submissions

Submit via OAKS as follows:

  1. Create a folder named 'First.Last', where 'First' is your first name, and 'Last' is your last name.
  2. Place your Java program inside that folder.
  3. Place your report (as a PDF file) inside that folder also. Name it, "Report.pdf".
  4. Compress the folder as a .zip file.
  5. Upload on OAKS.

Grading

Your grade will be based on how well you followed the above instructions, and the depth/quality of your work.

Reference

  1. Cooper, D. and Clancy, M. (1985) "Oh! Pascal", 2nd ed., W.W. Norton & Company, New York, p. 42.
(Printable View of http://www.cs.cofc.edu/~manaris/?n=Spring2016.CSCI230Homework5)