Efficient way of sorting a list of tuples in java

Question

Given is a generic datatype whick looks like this: HashMap<EdgeTuple, Double> edgeList where tuple is a class EdgeTuple and Double is a weight which is not important for the task:

class EdgeTuple{
    int label1;
    int label2;
    public EdgeTuple(int label1, int label2){
        int min = Math.min(label1, label2);
        int max = Math.max(label1, label2);
        this.label1 = min;
        this.label2 = max;
    }
}

So as you can see the tuples are already having the smaller value on first position. What I want to do is to sort the list which final entry order should look like this:

entry 0: [(0,something);some_weight]

entry 1: [(1,something);some_weight]

...

entry n-1: [(last_value,something);some_weight]

So basically what i need to do is to sort the tuples ascending on their first value. I have red the most liked existing answers on this topic but still could not find anything satisfying.

One possible solution is to lean on a comparator, something like this:

Comparator<Tuple> myComparator = new Comparator<Tuple>() {
    public int compare(Tuple t1, Tuple t2) {
        //the comparison rules go here
    }
};
Collections.sort(tupleList, myComparator);

The comparison of each pair of tuples does not seem quiet efficient. So my question is, do You know any other ways to sort? Maybe some new datatypes which provide a suitable more performant interface for the given task?

Thanks

The problem is that the comparator is in my opinion always working on each possible pair of tuples which is not in O(N) and not optimal — Jürgen K., Feb 01 '17 at 14:44
The comparator is used by whatever sort algorithm is used by Collections.sort(). If that algorithm is o(nlogn), then the compartor will be used that many times — David Zimmerman, Feb 01 '17 at 14:46
Collections.sort "This implementation is a stable, adaptive, iterative mergesort ... This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array." And if you want to know why mergesort http://stackoverflow.com/questions/32334319/why-does-collections-sort-use-mergesort-but-arrays-sort-does-not — awsome, Feb 01 '17 at 14:46

Vlad Bochenin · Accepted Answer · 2017-02-01T16:02:36.567

5

You can implements Comparable interface in your EdgeTuple:

public static class EdgeTuple  implements Comparable<EdgeTuple> {
    int label1;
    int label2;
    public EdgeTuple(int label1, int label2){
        int min = Math.min(label1, label2);
        int max = Math.max(label1, label2);
        this.label1 = min;
        this.label2 = max;
    }


    @Override
    public int compareTo(EdgeTuple o) {
        return this.label1 - o.label1;
    }
}

and use TreeMap to store presorted map of tuples and don't sort it every time.

edited Feb 01 '17 at 16:02

answered Feb 01 '17 at 14:49

Vlad Bochenin

3,007
1
20
33

Why "extends Tuple"? – Jürgen K. Feb 01 '17 at 15:59
@JürgenK. There is confusing part with Comparator in question, so I assumed that EdgeTuple extends Tuple – Vlad Bochenin Feb 01 '17 at 16:01
1

@JürgenK. I've removed this extends part – Vlad Bochenin Feb 01 '17 at 16:03

score 2 · Answer 2 · answered Feb 01 '17 at 14:51

Your sort is on integers between a pre-defined range, that qualifies for counting sort, which is faster then any generic sort algorithm.

You can use this implementation in Java, and adapt it for your Tuples: http://www.javacodex.com/Sorting/Counting-Sort

Here's a nice explanation + sample code: http://www.geeksforgeeks.org/counting-sort/

Efficient way of sorting a list of tuples in java

2 Answers2