java comparable error, stops sorting before complete

Question

I'm creating an object called 'Job', which i'm later going to want to sort ascending by how long each task will take (naming this variable "time"). In the class for job, i extended compareTo() as suggested by two tutorials, and now it looks like this;

public int compareTo(Job t) {
    int compare = ((Job) t).time; 
    return this.time - compare;
    }

or this;

public int compareTo(Job t) {
    return new Integer(getTime()).compareTo((t.getTime()));
    }

depending on which i comment out. Both implementations compile, but produce the same error, as follows.

In my main method, i made several jobs and added them to an array of jobs, Q[], also creating a int (length) to track how much of the array is non-null - how many actual jobs are in Q.

However, when i sort them with

Arrays.sort(Q, 0, length-1);

it only sorts until it finds that the 'next' object is larger than the current one. Here's a result from my last two tests, by (job name; job time):

jobA; 5,
jobB; 2,
jobC; 9,
jobD; 8.

sorting

jobB; 2,
jobA; 5,
jobC; 9,
jobD; 8.

---

jobA; 5
jobB; 2
jobC; 1
jobD; 8

sorting

jobC; 1
jobB; 2
jobA; 5
jobD; 8

I can provide more code if needed, but i'm not really doing anything else that should interact with this.

Answer 1

First, neither of those compareTo methods are (completely) correct:

public int compareTo(Job t) {
    int compare = ((Job) t).time; 
    return this.time - compare;
}

If the time values can be negative, then the subtraction can overflow resulting in a number with the wrong sign.

public int compareTo(Job t) {
    return new Integer(getTime()).compareTo((t.getTime()));
}

It is unnecessary (and wasteful) create and Integer instance. Use the static Integer.compare(int, int) method instead.

But neither of those issues explain the results you are seeing.

---

My guess is that the real problem is simply that length - 1 is incorrect.

According to the javadoc, the 3rd parameter of the Array.sort(...) methods is an exclusive bound. If length really represents the length of Q ... or the number of entries in Q that are valid ... then you should use length as the 3rd argument.

(The clue is that it is only the last element that is incorrectly sorted in your examples.)

Answer 2

Don't use int/Integer for time, use long/Long

Answer 3

You are calling Arrays.sort(a,fromIndex,toIndex) with the wrong toIndex:

You should call Arrays.sort(Q, 0, length);

Not Arrays.sort(Q, 0, length-1);

check: http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(byte[], int, int)

The range to be sorted extends from the index fromIndex, inclusive, to the index toIndex, exclusive.

So you are letting the last element out of the sort.