Is it better to use TreeSet or ArrayList when using a custom comparator

Question

I completed the schedule. I want to sort a given subset of vertices according to their degrees. So I wrote my own comparator with a name DegreeComparator.

private class DegreeComparator implements Comparator<Integer>
{
    @Override
    public int compare(Integer arg0, Integer arg1) 
    {
        if(adj[arg1].size() == adj[arg0].size()) return arg1 - arg0;
        else return adj[arg1].size() - adj[arg0].size());
    }

}

So which of the following methods is more efficient?

Using TreeSet

public Collection<Integer> sort(Collection<Integer> unsorted)
{
    Set<Integer> sorted = new TreeSet<Integer>(new DegreeComparator());
    sorted.addAll(unsorted);
    return sorted;
}

Using ArrayList

Collections.sort(unsorted, new DegreeComparator());

Please note that the second approach is not a function, but a single-line one.

Intuitively, I would prefer to choose the second. But I'm not sure if this is more efficient.

Answer 1

TreeSet is a collection. It removes duplicates (items with the same degree). So both of them are not equivalent.

, , , , . , , (O (n * log (n)) TreeSet, , , ( , , ).

Answer 2

API Java Collection Map, , . -,

Answer 3

, ArrayList . TreeSet , , .

, , .

---

, , ArrayList (, , ).

Arrays.binarySearch . , , , , . , , , Java TimSort, .

---

As stated in the comment, ensuring that it Comparatorreturns different values ​​is sometimes nontrivial. Fortunately, there is Guava Ordering#arbitrary, which solves the problem if you do not need to be compatible with equals. In case you do this, you can write a similar method (I'm sure I can find it somewhere if necessary).