V22.0101 ..... Homework 9 ..... Fall 2006
Sorting
Assigned: Mon Dec 4
Due: Tue Dec 12
Absolute deadline for late submissions: Thu Dec 14
Write a class with the following sorting methods
- a selection sort method to sort an array of doubles
- a selection sort method to sort an array of Comparable objects
- a merge sort method to sort an array of doubles
- a merge sort method to sort an array of Comparable objects
Sort into ascending order.
When you sort the doubles, use the ordinary comparison operator "<" or ">".
This means that if there are any NaNs in the input they may end up anywhere in the sorted
order, but that's OK. (This is because when anything is compared to NaN, the result
is false). The order of 0 and -0 does not matter since
their values are the same. The objects must be from a class that
implements the Comparable interface, so that you can call their compareTo method.
Each of the selection sort methods should work with only one array.
Each merge sort method must use recursion and should
work with only two arrays. How to accomplish this
will be explained in class.
A main program should give the user a choice of sorting
- doubles
- Double objects using the Double wrapper class (this implements Comparable)
- Date objects (as in HW4)(we implemented Comparable for this on Nov 8)
- some other class of objects that implements Comparable: your choice
It should also ask the user how many items there are to sort, so that
it is efficient to use arrays (as opposed to ArrayLists).
The program should then construct the appropriate array and
ask whether the user wants the program
to read the data to be sorted from a specified file, or from System.in, or
wants the program to generate the data randomly. If the user chooses
to input the object data, each object should be entered one per line.
Be sure to prompt the user how to do this, e.g. year, month, day for
Date objects. Use try...catch to catch input format errors and insist
on correct formatting. (See class program from Nov 30.) If there are not enough
lines in the file, throw an exception. This can't happen with System.in,
because there are always more lines in System.in. If there are too many lines
in the file, print a message that you are ignoring the rest of the data.
After reading the data, call 3 sorting
routines to sort the data: your selection sort method, your
merge sort method, and the sort method in the java.util.Arrays class. Measure
the running times using System.currentTimeMillis and print how long each sort
takes. Ask the user if he/she wants to see the items printed in sorted order.
Answer the following questions in your email cover note.
Do you see a big difference in efficiency between
- Your selection sort versus your merge sort?
- Your merge sort versus the java.util.Arrays sort?
- Sorting doubles versus sorting Double objects?
Make sure you've chosen the number of items large enough to see a difference
if there is one - use the random generation option for this.