2

I wrote a comparator for a custom class of mine and when I ran my code I realised the output of my list of these objects was in the reverse order as to what I wanted. It was "ascending" as opposed to "descending". This was because I stuck to the spec of compare where a return value of less than 0 means the other object is less than this and so on.

To fix this I called the reverse method on my list, but I could've also changed the compare method so that it returns greater than 0 where the other object is less than this.

What is seen as the standard for this case and why?

0

Start by ignoring any performance impact of reversing the list. Any sensible list-reversal will be linear in time, which means that for large lists, the sorting will dominate.

If there is a "natural" ordering of your elements (i.e. an ordering which is independent from your particular implementation), I would recommend sort + reverse. This will make the comparator easier to reuse, and it will be easier to understand the code which invokes the sort. Compare these two:

x = <array of integers>
x.sort(NaturalOrdering)
x.reverse

and

x = <array of integers>
x.sort(MyOrdering) // what ordering is this?

If there is no natural ordering (i.e. you are imposing an "artificial" ordering just to be able to sort elements), it probably makes more sense to have the comparator return the desired ordering directly.

If you are tempted to start optimizing at this point, please measure the code before and after you optimize. It is never obvious which implementation is the faster one.

1
  • "Premature optimisation is the root of all evil". Although I would prefer to stick to the convention.
    – GKruger
    May 7 '13 at 17:26
5

Your real problem is that you're using the wrong sorter. Your comparator is correct, and (depending on the language) it may wind up being used for other cases where the comparison should not be reversed. Instead of "fixing" (actually breaking) the comparator, you should find out how to get the sorter to sort in descending order. Any decent sorting library will have that option.

2
  • Good answer. Although as others have put it, it does matter whether I'm using imposing a natural or artificial ordering
    – GKruger
    May 7 '13 at 17:29
  • I disagree. It would be much better to have a comparator that takes as input another comparator but with its output swapped. May 7 '13 at 18:03
1

Use comparator with correct order for your application. Sorting and then reversing means that you are doing the sorting AND going through list again to reverse it.

When you are creating comparator, you are defining new ordering and YOU are difining what value is lesser and what higher. Eg. in reverse ordering of natural numbers, 10 is less than 9 even though in the usual ascending order 10 is greater than 9.

3
  • 3
    I would reformulate the second paragraph. The comparator does not say which value is less, but it indicates which value comes first in the ordering. May 7 '13 at 7:51
  • @BartvanIngenSchenau Imo its the same in different words. Its like defining what + and * means in body. We call them addition and multiplication even if they numericaly do something else. And I used these words because "Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second." is used in javadoc.
    – user470365
    May 7 '13 at 8:22
  • It is indeed the same in different words. I suggested them because it was words like in the javadoc that caused the confusion of the @OKruger in the first place. May 7 '13 at 8:59
1

If you already have written a comparator, it's of course best to modify it so that the standard sort (into "ascending" order) does what you want.

The second best thing is to use whatever switches or tricks are available in your language's standard sorting methods. Such as this in Java:

Arrays.sort(array, Collections.reverseOrder());

The third option, reversing an already sorted list, isn't a categorically bad solution. In some cases it's the simplest possible solution, and easiest to comprehend. The efficiency overhead of reversing an array/list is negligible in majority of cases.

1

Comparer which makes it sorted in the right order is better. When you already use comparer (and you do in this case) it is better (faster/more by-the-book) to modify the comparer (or create another one).

Although, when sorting object which have "natural" comparison (for example: int) and "standard library" (for example: BCL for .NET) which can leverage this it might be faster to sort in natural order than reverse.

For example (C#), having:

int[] data = new int[1000000];
Random rand = new Random();
for (int i = data.Length - 1; i >= 0; i--) data[i] = rand.Next();

sorting than reversing:

Array.Sort(data);
Array.Reverse(data);

will be must faster than:

Array.Sort(data, (a, b) => b.CompareTo(a));

It is not your case though, I just mentioned it for completeness.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.