Comp 271 lab 3 - A Race of Sorts
Goals
- Implementing selection and insertion sort (not to worry -- you can cut and paste from the book)
- timing comparisions between sorts
Overview
I've given you an outline project that has a SortTester class and one sort implemented
-- bubble sort. You are to create classes for selection sort (Bailey
6.2, p 122) and insertion sort (6.3, p 125) (just cut-and-paste-and-edit-as-necessary
from Bailey), and then use the timing stuff in SortTester
(specifically, System.currentTimeMillis()) to establish relative times
for the different sorts and different data sizes.
You are also to write a method sortVerify(int [] A, int len)
that returns true if A[0] through A[len-1] are sorted (ie A[i] <=
A[i+1] for 0<=i<len-1), and false otherwise, and use this method
to verify that your sort classes are working.
Be prepared to fill in the following table of sort times (in milliseconds, or seconds to three places).
size
|
bubble sort
|
selection sort
|
insertion sort
|
1000
|
|
|
|
2000
|
|
|
|
4000
|
|
|
|
8000
|
|
|
|
12000
|
|
|
|
16000
|
|
|
|
Note that the times might change considerably
if we were sorting more complex data -- say Strings --- because
comparison of String data is more expensive than for int. Also, be sure
that you are not timing anything except the sort (for example, do not
include the sortVerify).
Also tell me how much variability
there is in the sort times (for all but the largest sizes, perhaps you
should have your program run the entire test several times).
See also the Bailey section How Fast is Java, starting on page 115.
To submit your project, create a zipfile and email it to me at
pld@cs.luc.edu. Note that you will also have to add a text (or word, or
openOffice, or html) file that contains the results of your testing.