This assignment is to run a variety of programs which sort
an array of integers and evaluate their running times
for different sizes of arrays.
You will be given a class for each different sorting algorithm.
Each class has a method called sort which takes
as input an array of integers. This function will copy the array
of integers into a new array and sort the integers in the new array.
If you want to retreive the array of sorted integers, you can use
the method getSorted , but that should be unnecessary
for this assignment.
You will also be provided with a class FileReader
which has a method called readFile . The method
takes a String as a paramter. The method will open the file with
that name and read its contents. The method will assume that
the file consists of a series of integers, one to each line.
The first number indicates the number of integers in the rest
of the file.
The method will read in all the numbers and place each integer
(except the first) into an array and return the array.
If the file has an incorrect format, it will return a null array.
Your assignment is to write a Java application which will run each
sorting algorithm on each of the data files provided below.
You should calculate the time that each run took and print out
the running time.
To get the running time, you will need to use class
Calendar . The static method getInstance
will return the time that the call was made
in the form of an instance of class Calendar .
The getTime method of Calendar returns an instance
of class Date . The getTime method
of class Date returns a long which contains the number of milliseconds
since January 1, 1970. You should measure the running time of the
sorting algorithms in milliseconds.
If it happens that the time is too short to measure in milliseconds,
you can run the algorithm multiple times and calculate the average
running time for the multiple runs.
Note: you can run your experiments on any machine. You can also run them in the debugger or not. However, you should keep the conditions consistent throughout the experiments.
You should turn in an electronic copy of your code. In addition, you should prepare a brief report on your experiments. The report should include a short description of the experiments run. You will also be asked to plot your data in the form of a graph. You should format this graph in a way which makes it as easy as possible to interpret the data. Finally, you should discuss your conlcusions about the asymptotic running time of each algorithm. In particular, which ones have the same growth rate. Which ones would you use in which circumstances?
The report should read as an independent document. That is, it should not depend on this lab assignment page in any way. The report should also use gramatically correct English and be written in full sentences.
Here are the java files you will need:
Here are the data files you will need: