Due Date:
Thursday, February 5
File(s) to be submitted:
GeneralSorting.java
Sample Output:
SampleOutput.html
Starter Files:
Summary
Download all four starter classes. There is one program class (GeneralSorting), one helper class (Common), and two data type classes (Person and Student). You need them all in order to run the program.
GeneralSorting is supposed to demonstrate four sorting methods on four different kinds of array. But it's currently un-compilable, because the sorting methods accept only
int[]s.Revise the sorting methods in GeneralSorting so that they can be used on any sortable array of objects.
Even tho' each sorting method is called on only one kind of array, all four sorting methods need to be revised so that they can be called on any sortable array. Don't make the mistake of thinking that once your revised program produces the correct output that you're done!The amount of programming you need to do for this assignment is quite small. Only a few lines of code need to be changed. All of the changes are in GeneralSorting, and only the four sorting methods (
bubbleSort,selectionSort, etc.) in it.The important task here is to understand what it is you're doing. The details section below explains what you need to know. (The amount of reading you need to do is quite a lot more than the amount of programming!)
The online code I have provided for sorting
only works with int arrays.
In L03
I asked you to revise one of them to sort String objects.
In this assignment I ask you to take it all a step further:
make them work for any sortable array of objects.
I have provided you with a revised version of the class Common.
This has made all the swap and printArray methods
fully general:
they will work with any array of objects.
I did that by adding a type parameter
to each method.
Instead of
The only method where there is a T inside the body of the method
is the swap method.
In that method the line that used to read
int[],
temp needed to be an int variable.
But with an Integer[]
it needs to be an Integer variable;
with a String[]
it needs to be a String variable;
with a Person[]
it needs to be a Person variable;
and so on.
By making the type a variable (T)
Java can match the types automatically:
with a T[] (unspecified base type)
temp needs to be of type T
(unspecified, but same as the base type of the array).
For Common that's all that's required.
But for sorting there's more to it.
In order to sort an array,
the sorting method needs to call the compareTo method.
The only classes guaranteed to have a compareTo method
implement Comparable.
The computer can sort String[]s
because String implements Comparable<String>.
The computer can sort Person[]s
because Person implements Comparable<Person>.
So it seems that,
in order for a T[] to be sortable
it needs to implement Comparable<T>.
How do we tell Java that?
We need to add a constraint on the type parameter.
You might think we should do this:
implements
we need to write extends:
That'll work for the Integer[], the String[], and the Person[]. But it won't work for the Student[].
Every Student is a Person, and so we can compare Students by name by calling
Nevertheless, if you try to sort a Student[] using the code I described above, you'll get an error message. The problem is that Student doesn't implement Comparable<Student>; it implements Comparable<Person>. The constraint
Fortunately Java allows us to state the constraint we actually need:
So, that's the incantation you need in order to say that the data type T needs to be sortable. NOTE that in every other part of the method the data type is just referred to as T. The constraint appears only in the parameter type declaration: