Hey, so yeah, I'm doing some project with Comparable interfaces and the sorting of various objects... and I decided, hey, we just half learned merge sort in class, why don't I figure out the rest of it and use it here. Of course, me trying to figure it out on my own seems to have led to some problems.
I have not used the Comparable interface before either, since we are just learning it, so perhaps I have that wrong as well...
Well, let me see...
Here is my sorting class:
public class Sorter {
//---------------------------------
// Sorts an array using merge sort.
//---------------------------------
public static void mergeSort(Comparable[] objArray, int left, int right) {
int mid = -1;
if (left < right){
// Finds the middle:
mid = (int) (left + right)/2;
// Calls mergeSort twice:
mergeSort(objArray, left, mid); // Sorts first half.
mergeSort(objArray, mid+1, right); // Sorts second half.
// Calls merge (sorts 2 sorted subarrays and makes into one array)
merge(objArray, left, mid, right);
}
}
//----------------------------------
// Merges two sorted subarrays into
// one sorted array.
//----------------------------------
private static void merge(Comparable[] objArray, int left, int mid,
int right){
int length1 = mid - left + 1; // Length of first subarray.
int length2 = right - mid; // Length of second subarray.
// Counters for merging.
int count1 = 0;
int count2 = 0;
int sortedCount = 0;
int i = 0;
// New merged sorted array:
Comparable[] sortedArray = new Comparable[length1+length2];
while ((count1<length1) && (count2<length2)){
//If obj in subarray1 is less than obj in subarray2:
if (objArray[left+count1].compareTo(objArray[mid+count2+1])<0){
sortedArray[sortedCount]=objArray[left+count1];
count1++;
}
else {
sortedArray[sortedCount]=objArray[mid+count2+1];
count2++;
}
sortedCount++;
}
// If one subarray is done being merged, apped the remainder of the
// other array to the sorted array:
while (count1<length1){
sortedArray[sortedCount]=objArray[left+count1];
sortedCount++;
count1++;
}
while (count2<length2){
sortedArray[sortedCount]=objArray[mid+count2+1];
sortedCount++;
count2++;
}
// Put sortedArray back into original array.
for (i = 0; i < length1+length2; i++)
objArray[left+i] = sortedArray[i];
}
}
Right, and then we're supposed to take an older class for cards from a previous project, and make it use the comparable interface so we can sort it...
So I put the following lines into the code:
public class Card implements Comparable {
and
public int compareTo(Object otherObject){
Card other = (Card) otherObject;
int answer = 0;
if (this.rank > other.rank)
answer = 1;
if (this.rank < other.rank)
answer = -1;
return answer;
}
so that's that...
Then, just to test it, in my driver I made an array of cards and put it into Sorter.mergeSort(); and tried to print the results. When I compiled and ran I got:
Exception in thread "main" java.lang.NullPointerException
on several different lines. Any idea why that might be?
Also, what we're actually supposed to be sorting isn't just an array of cards but a deck object from last project... the deck is an array of cards though. Can I just instantiate a deck, and plug it into merge sort, and it should work?
I'm still working on some other things as this is going on. We also need to be able to sort BankAccounts.
Also, I was wondering how one could make it sort by two different things, rank and suit, this way... would I need to change the compareTo method in my card class? I figured out how to sort by rank and suit using a method I had put into the Deck class, but we need to use a general sorting static method.
Oh boys.
Not asking for anyone to do my HW of course though, just trying to learn and figure out what I am doing wrong with what I already have.
Posts
Edit: Also, NullPointerException means you're trying to access an object that isn't created. For example:
If you're submitting this for marks you've got a couple of stylistic problems that could cost you some points. Some pointless type casts and redundant variables in various spots where you could express what you're doing much more cleanly.
And I've had profs that would fail you for the way you're commenting things; always use comments to tell someone why you're doing something, not what you're doing. Sticking a comment on a function call that consists of "calls function" or an "is x less than y" comment on an if statement isn't just poor style, it actively distracts from the actual code which already documents precisely what it's doing. Tell your readers why you're call function, or why you're checking to see if x is less than y.
Cleared up the redundant casting... when you say some variables are redundant, do you mean things like sortedCount, which I realized I could just have as count1 + count2?
EDIT: Yay, I made it work. It sorts my deck of cards. However, perhaps this is a roundabout way of doing it....
Here is part of my code:
could be expressed as
The advantages here are the lack of an variable and the fact that by returning immediately out of the if statement rather than at the end of the function the effect of the if statements is immediately clear. Even if you wanted to keep around the additional variable to store the value you want to return, you'd be better off sticking an else clause in, like:
Without that else in there, even after finding out that this.rank really is greater than other.rank, you're performing the second test anyways, which is redundant. I think this is less clean than eliminating the answer variable, though, because the fact that it returns 0 if both the greater than and lesser than tests fail is less immediately explicit to the reader.
The redundant cast was simply "mid = (int) (left + right)/2". mid is an int, so the conversion to an int was guaranteed even without the cast.
When comparing multiple values, I try to avoid multiple else if statements. Plus, this way is slightly more efficient, which is important if you're comparing hundreds of values.
And don't forget, compareTo doesn't return ONLY 1,0, -1. As stated in the javadoc
"Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object."
This is important for figuring out relative differences in two comparable Objects without looking at them. So try to avoid the habit of only using 1,0,-1.
Well, the problem with using subtraction is that you can have an overflow. For example, a signed byte can have values from -128 to +127. If you try to subtract +127 from -128, you will either get +1 or some sort of overflow exception. In a lot of situations it may not matter, but it's something to keep in mind.
Admittedly, thats an issue. But I was under the assumption that his suit and rank wouldn't be from negative integer max value to positive max value. Though I wont deny there isn't much difference when we're comparing two primitives.
Plus this shorter way of writing compareTo works well for general Objects that are comparable, which is generally when you use mergeSort and the like. For example, for a Pair Class that contains comparables:
(Ignoring Generics)
is more efficient than:
My point is that not to pick up bad habits like using multiple compares when you might not need to. Sometimes people pick up bad habits when they first start coding. The difference in efficiency is especially true when what your comparing might take a while to finish comparing. If the OP is learning sorts, he should be learning about coding efficiency and Big O. ( Yes, I know both ways are O(n). But one is O(2n) and O(4n). It makes a difference to a CprE. )