Assignment 8

The Assignment

http://www2.hawaii.edu/~tp_250/ICS211/Fall03/hw08.htm

Comments

For testing, I recommend you use System.currentTimeMillis() to get the current time before and after running each test to find out how long it took. (See Assignment 2 for an example of this.)

I would prefer that your program tested the sorts in you main method and printed the results. However, if you'd really rather write a report instead, that will be fine.

To generate random strings, I recommend you create them from an array of random chars. To create a random char, create a random number (num) between 0 and 25 (or more), and then you can cast it to a char using the line:

char random = (char) ('a' + num);

You may find some use in the StringBuffer class as well.

(Note: My previous recommendation of using Character's forDigit was incorrect. I didn't read the documentation close enough; forDigit does not do what I thought it did. Thanks to Shim for suggesting a good alternate technique.)

Grading

This assignment will be out of 10 points. You will get points for the following:

2.5 - Your program compiles without error

1.5 - Good documentation and follows ICS Java Coding Standards.

See this note on documenting your code. Use descriptive variable names, use internal capitalization for names, consistently indent and space code, etc.

1.5 - InsertionSort

Correctly implemented.

1.5 - QuickSort

Correctly implemented.

1.5 - MergeSort

Correctly implemented.

1.5 - Testing

• Use at least 3 sets of random integers and 3 sets of random strings for each sort. How do the sorts compare to each other?
• Does it matter if you sort Strings or ints?
• How much better is Insertion sort with "best case" input, rather than random input?
• How much worse is QuickSort with "worst case" input, rather than random input?