Java: reverse sorting without keeping the order

Question

Update: In fact, the only acceptable solution for this problem would be sorting the array ascending and then reversing it.

Let S be the following sequence of events:

Event | Time
  A   | 0:00
  B   | 0:01
  C   | 0:01
  D   | 0:02

I have a simple Comparator to sort S, which sorts the elements according to the time value.

public int compare(Event e1, Event e2) {

    // Reverse sorting. 
    // _sortOrder is set outside this method.
    if(SORT_DESCENDING.equals(_sortOrder))
        return e2.getTime() - e1.getTime(); /* time is long */

    return e1.getTime() - e2.getTime();
}

The problem is: when the sort order is ascending, S is sorted correctly: A, B, C, D.

But when I use reverse sorting, S becomes D, B, C, A:

Event | Time
  D   | 0:02
  B   | 0:01 /* B and C should be reversed */
  C   | 0:01
  A   | 0:00

This happens because the default sorting algorithm keeps the original order for elements with the same time value.

So, how do I sort it reverse without keeping the original order?

Note: I know I can sort S ascending and further simply revert it, but unfortunately this is not an option in my case.

Answer 1

Why the B and C should be reserved? What is the order criteria?

Answer 2

Why is 0:01 smaller/larger than 0:01, or why should it be sorted in a very special way if they’re both the same?

You’re not looking for a reverse sort, you’re looking for a reversed sort, sorry. :)

Answer 3

What are you using to sort? My guess is it's something which guarantees it's a stable sort - and you've got two equal values, as far as the comparison is concerned.

Is there any additional ordering you can impose in this case? Can you easily tell which event would come first in the ascending ordering? If so, just make the original comparison use that as well, and then your descending ordering will start to work naturally.

EDIT: As your data doesn't have any extra ordering information in it, I wouldn't be surprised if it were returned in different orders when you performed the same query again in Oracle. However, if you only care about the order in this one particular case, I suggest you add an extra field in your Java in-memory representation to store the original index in the loaded list - as you read the data, keep track of how many you've read and assign the field accordingly. Then you can use that when you sort.

Answer 4

The sorting algorithm is correct: 0.01 is 0.01. Unless there's something you're not telling us. If however you want the exact reverse order of an ascending sort then sort them in ascending order and use Collections.reverse(). By this I mean:

List<SomeObject> list = ...;
Collections.sort(list, myComparator);
Collections.reverse(list);

which will give you exactly what you want.

But if reversing isn't an option you only have two options left:

1. Make it so no two elements can be "equal". Either include another field or add a synthetic one (such as the current index or the primary key if it is a number). This will give you a reproducible, consistent and mirrored order; or
2. Implement your own sorting algorithm. This is not recommended as it's simply too error prone.

Now before you say you can't reverse (why?), let me ask you how you're sorting? if you're using Collections.sort() consider the source code (Java 6u10):

public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
    i.next();
    i.set((T)a[j]);
}
}

So it copies the collection into an array, sorts that array and then uses that to reorder the collection.

Are you sure you can't afford a reversal?

Answer 5

I think what you really want is a secondary sort criteria, such that you can sort the items even if the primary sort criteria considers the items equal. In your example, the primary criteria would be time, and secondary would be Event. This way, you don't have to rely on the items being in a certain order before performing the sort, which makes things a lot easier.

If you really don't have a secondary criteria, you would likely need to look into stable vs. unstable sorting algorithms, like Jon Skeet mentioned.

Answer 6

Am I missing something, or couldn't you just use the event name (or whatever A, B, C and D are) as secondary sort key? Just extend your Comparator to something like:

public int compare(Event e1, Event e2) {
    int cmp = e1.getTime() - e2.getTime(); // compare times
    if (cmp == 0)  // if times are equal, compare names instead
        cmp = e1.getName().compareTo(e2.getName());
    return SORT_DESCENDING.equals(_sortOrder)? -cmp : cmp;
}

Answer 7

Sort order does look correct, just compare the names if e1.getTime() == e2.getTime().

Answer 8

Depending on how fast comparing two elements is in comparison to switching them, you could just do a descending stable sort, and then reverse only all regions of "equal" elements.