java sorting issue

Question

I have a arraylist of a POJO and the data in it is of the form

id    time
2     467
3     403
4     602
3     529
5     398

The requirement is that first I need to sort the data by time and then after that the same IDs should be one after the other i.e

id     time
5      398
3      403
3      529
2      467
4      602.

Initially to sort by time , I'm using the following logic

Collections.sort(list, new Comparator<Asset>() {
                    @Override
                    public int compare(Asset o1, Asset o2) {

                        if (o1.getTime() > o2.getTime())

                            return -1;

                        else if (o1.getTime() < o2.getTime())

                            return 1;

                        else

                            return 0;

                    }

                });

Could some one help me in clubbing by IDs in the next stage?

Answer 1

Since Collections.sort(...) is guaranteed to be a stable sorting algorithm you can simply go and first sort by time and then sort by id.

Stable sorting guarantees that equal elements remain in the same order as before.

For your example:

1. sort by time
2. sort by id

After first step all your times are sorted. After the second step your collection is sorted by id - and for equal ids they remain in the same order since the sorting is stable.

So for same ids they are still sorted by time in the second place. You can drive this up to as many sortings as you like without holding any state of previous sortings. And that's only because you're using stable sorting.

Output

2  467
3  403
3  529
4  602
5  398

Answer 2

To sort the data according to the example you gave, you probably need two passes over the list. (How else would you determine whether or not 3 504 should come before or after 5 315?)

1. Sort according to time.
2. Sort the list according to the first index of each id.

Here's some sample code:

import java.util.*;

class Asset {
    public int id;
    public int time;

    public Asset(int id, int time) {
        this.id = id;
        this.time = time;
    }

    public String toString() {
        return id + "  " + time;
    }
}


class Test {
    public static void main(String[] args) {

        List<Asset> assets = new ArrayList<Asset>();
        assets.add(new Asset(2, 467));
        assets.add(new Asset(3, 403));
        assets.add(new Asset(4, 602));
        assets.add(new Asset(3, 529));
        assets.add(new Asset(5, 398));

        // Sort according to time.
        Collections.sort(assets, new Comparator<Asset>() {
            @Override
            public int compare(Asset o1, Asset o2) {
                return new Integer(o1.time).compareTo(o2.time);
            }
        });

        // Remember the original indexes of each asset.
        final List<Asset> assetsCopy = new ArrayList<Asset>(assets);

        // Sort the collection based on the index of the first asset
        // with the same id
        Collections.sort(assets, new Comparator<Asset>() {

            private int firstIndexOf(int id) {
                for (int i = 0; i < assetsCopy.size(); i++)
                    if (assetsCopy.get(i).id == id)
                        return i;
                return -1;
            }

            @Override
            public int compare(Asset o1, Asset o2) {
                return new Integer(firstIndexOf(o1.id))
                        .compareTo(firstIndexOf(o2.id));
            }
        });


        for (Asset a : assets)
            System.out.println(a);
    }
}

Output:

5  398
3  403
3  529
2  467
4  602

Answer 3

below code is an example. The idea is to check if the times are equal, if they are sort on id, else sort on time.

Collections.sort(list, new Comparator<Asset>() {
     @Override
     public int compare(Asset o1, Asset o2) {
         if(o1.getTime() != 02.getTime()) {
             if (o1.getTime() > o2.getTime())
                 return -1;
             else
                 return 1;
         } else {
             return new Integer(o1.getId()).compareTo(o2.getId());
         }
     });