CODEWITHSUNDEEP
javaalgorithmsorting
NeplatnyUdaj
NeplatnyUdaj

Reputation: 6242

More efficient sort algorithm?

I'm looking for an algorithm, which could perform better, than Arrays.sort(). I know this will look like a silly question asked million times, but please read on.

Let's have two classes implementing Comparable whose natural ordering is based on an int value. The first compareTo method looks like this: 

 public int compareTo(ComparableInteger o) {
     return this.value - o.value;        
 }

The second is this: 

public int compareTo(ComparableInteger o) {
    if (this.value > o.value) {
        return 1;
    } else {
        if (this.value == o.value) {
            return 0;
        } else {
            return -1;
        }
    }
}

When I call Collections.sort on list of instances of these clases, they both perform about the same.

My question is if there is a sorting algorithm, which would benefit of the added information of the first compareTo method. In the first example, the added information is this:

Let's have three values of ComparableInteger:

a == 1
b == 2
c == 3

Now when we compare c to a, we get 2 and when we compare c to b we get 1. From the compareTo implementation it is clear, that the b should go after a, because c.compareTo(a) > c.compareTo(b) so we know the correct order. The existing Comparable contract doesn't require this and needs another comparison. For example following implementation also fulfills(at least I hope) the contract, but gives different result(numbers sorted, but even numbers are before odd numbers)

public int compareTo(ComparableInteger o) {
    if (value % 2 == o.value % 2){
        return value - o.value;
    } else {
        if (value % 2 == 1){
            return 1;
        }else{
            return -1;
        }
    }
}

Upvotes: 4

Views: 2260

Answers (5)

zstewart
zstewart

Reputation: 2177

There are a lot of things which the efficiency of a sorting algorithm could depend on, but one thing to note is that in general, if you are sorting based on comparisons between elements, the fastest possible asymptotic runtime is Ω(n lg n).

It is, however, possible to construct a scenario where sorting can be done faster than n lg n, but this requires using more information than just comparisons. These are the so-called "linear sorts", which sort by using the value of the element rather than a comparison to another element. Examples of these are Bucket Sort, Counting Sort, and Radix Sort.

The first comparison method you provided does provide extra information, which might enable a faster sort speed, but only under constrained conditions. If, for example, you know that there are no duplicate values, and that every value between the minimum and maximum value is used exactly once, then you could perform a sort by:

  1. Performing a linear search to find the minimum.
  2. Comparing each element to the minimum and placing at the index given by the comparison method.

This method should take 2n = O(n) time. Of course, unless the objects contain extra information besides the integer value, you could just construct the range min..max directly. Also, if you can read the integer values of the elements, you could just implement a normal bucket or counting sort on them.

tl;dr: The fastest possible comparison based sort is Ω(n lg n). It is possible to sort faster when you can read the exact value of an element, but linear sorts are only work in certain constrained circumstances. In general you should just use your programming language's builtin sort.

Upvotes: 4

Mark Stewart
Mark Stewart

Reputation: 2098

Always stick with the core Java Collection features such as Arrays.sort() as they have been tested for all kinds of nuances that have been noted in the answers so far, that most programmers aren't likely to think of, and they are also tuned for performance. And when the next version of Java comes out, you won't have to re-test your own sort routine.

Upvotes: 0

ryanyuyu
ryanyuyu

Reputation: 6486

Be careful with the first Comparison, it is not perfectly consistent. 

 public int compareTo(ComparableInteger o) {
     return this.value - o.value; //not always correct
 }

As Eric Lippert points out (the article is for C#, but still valid for Java), you first Comparison is unsafe:

In particular, for the inputs Int32.MinValue and Int32.MaxValue, the difference is 1. Clearly the smallest possible integer is smaller than the largest possible integer, but this method gives the opposite result!

As you mentioned, other overflow/underflow problems arise as well.

So in fact, it would take more logical overhead outside the comparison for any sorting algorithm to try to use the "extra" information. The "extra" information comes at the cost of some extra headaches and corner cases.

Upvotes: 2

Marcin Szymczak
Marcin Szymczak

Reputation: 11433

  • Normal algorithm: 3 comparisons

  • Your algorithm: 2 comparisons + 1 comparison of 'cached' values of previous differences. (in your example checking that 2>1 which will determine order of a and b)

As for O complexity they are the same, but my feeling is that your implementation will be bit slower in practice (and bit harder to implement).

Upvotes: 1

Scott Hunter
Scott Hunter

Reputation: 49803

I don't think the extra information in the first compareTo is as useful as you think: in your example, you have merely replaced a comparison between objects with a comparison between results of compareTo, and that will be the case regardless of sorting algorithm.

Upvotes: 1

Related Questions