CSC 427: Data Structures and Algorithm Analysis
HW3: Sorting & Efficiency
For this assignment, you will compare the performance of various sorting
algorithms. In order to time the different sorts, a
StopWatch class has been provided for you.
This class models a simple stopwatch, which you can start before executing a piece
of code and then stop afterwards to measure the elapsed time.
StopWatch timer = new StopWatch();
// CODE TO BE TIMED
System.out.println("Elapsed time (in msec): " + timer.getElapsedTime());
- (40%) Write a class named SortTimer with a main method that does the following:
- Prompt the user for a list size (e.g., N = 10,000).
- Create an ArrayList of the Integers from 1 to N, in random order.
Note that you can do this by first putting the numbers in the list in order, then
calling Collections.shuffle on that list.
- Create a stopwatch and use it to time the execution of the Collections.sort
method on your list.
Note: a text-based interface is fully sufficient here. For up to 5 extra
credit points, you can create a graphical user interface that is more attractive and
easier to work with.
- (20%) Using your SortTimer class, measure the performance of Collections.sort
on lists of increasing sizes. Since the timings provided by the StopWatch class
are somewhat imprecise (they can be affected by garbage
collection and other tasks sharing the CPU), you will want to do several executions at each size
to account for variation. For example, you might produce a table of results similar to the following
(which contains purely fictional data):
|list size||execution 1||execution 2||execution 3|
Depending on the speed of your computer, you will need to select file sizes that produce
timings that are reasonably differentiated. You will also need to continue increasing
the file size until the performance pattern stabilizes.
Report your timing data. Do your timings support the claim that the Collections.sort algorithm
uses an efficient O(N log N) sort? Justify your answer.
- (10%) Static methods for performing selection sort and merge sort are provided in the
in Sorts class. Similar to how you measured the
performance of Collections.sort in the previous problem, measure the performance of
selection sort. As before, you will need to
select appropriate sizes and increase the sizes until the performance pattern stabilizes.
Report your timing data. How do these timings compare in absolute terms with Collections.sort
on lists of equivalent sizes? Do your timings support the claim that the selection sort
is an O(N2) sort? Justify your answers.
- (10%) Similarly, measure the performance of the merge sort algorithm and report your timing data.
How do these timings compare in absolute terms
with Collections.sort and selection sort on lists of equivalent sizes?
Do your timings support the claim that the merge sort is an O(N log N) sort? Justify your answers.
- (20%) As we discussed in class, big-Oh characterizes the efficiency of an algorithm
in the long run. It is certainly possible that the constants and high overhead
of an O(N log N) algorithm can make it slower than an O(N2)
algorithm on small problems. Modify the merge sort code in the Sorts class
so that selection sort is used when list size becomes small. For example, if the recursion
in merge sort gets down to a list of size 5, you could avoid further recursion and simply call
selection sort to handle the rest. The threshold for switching to selection sort should
be a constant, defined at the top of
the Sorts class (so that it is easy to find and change, if desired).
Time your modified merge sort on a large list and compare its performance relative to the
standard merge sort. Does switching to selection sort at size 5 improve overall performance?
Is there an optimal threshold that produces the best performance? Report your data and
provide explanations to support your claims.
Turn in your
SortTimer and modified
Sorts classes, along with your
timings and commentary.