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?
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
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
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
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.
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.