CODEWITHSUNDEEP
javalistsortingarraylistdata-structures
KDX2
KDX2

Reputation: 1023

Sort List<List<Integer>> by first number in each sub-list

I came across the following problem. I have an ArrayList(1) of ArrayLists(2). What I need to do is, to sort the structure so that the first elements of ArrayLists(2) to be in ascending order going down ArrayList(1). To clarify:

Input:

3, 8, 6
2, 14, 205, 44, 1
1, 3

Output:

1, 3
2, 14, 205, 44, 1
3, 8, 6

Look how it sorts the rows only based on the first value.

For now the way the arraylist of arraylists is defined for me is:

List<List<Integer>> graph = new ArrayList<List<Integer>>();
// and I add elements to it likewise
graph.get(currentIndex).add(new ArrayList<Integer>());

The reason I am using ArrayList is because I read that it is more memory efficient than LinkedList and because I am building a list of adjacency lists of a graph. In it both either the number of nodes can vary or the length of the adjacency list per node. The first element of a row is the start_node, the following - its adjacent. Could you please tell me how can I implement this sorting?

Upvotes: 3

Views: 3461

Answers (3)

KDX2
KDX2

Reputation: 1023

So, here is another solution I came up with.

The idea is: use the Collections' static method sort() and feed it in with the reference to the list and a new Comparator object with defined by us compare().

Collections.sort(graph, new Comparator<List<Integer>>(){
@Override
public int compare(List<Integer> aList1, List<Integer> aList2) {
   return aList1.get(0).compareTo(aList2.get(0));
}
}));

Upvotes: 0

azro
azro

Reputation: 54148

To compare 2 sublist you need to find the first non-equal pair, and compare their value (if both starts with like 32, you need to look next value to see)

List<List<Integer>> graph = new ArrayList<>();
graph.add(Arrays.asList(3, 8, 6));
graph.add(Arrays.asList(2, 14, 205, 44, 1));
graph.add(Arrays.asList(2, 14, 205, 44, 2));
graph.add(Arrays.asList(1, 3));
graph.add(Arrays.asList(1, 4));
graph.add(Arrays.asList(1, 4));
graph.add(Arrays.asList(1, 4, 5));

graph.sort((o1, o2) -> {
    int indice, cmp, min;
    for (indice = 0, min = Math.min(o1.size(), o2.size());
         indice < min; indice++) {
        if ((cmp = Integer.compare(o1.get(indice), o2.get(indice))) != 0) {
            return cmp;
        }
    }
    if (indice == o1.size()) return -1;
    if (indice == o2.size()) return 1;
    return 0;
});

System.out.println(graph);

[[1, 3], 
 [1, 4], 
 [1, 4], 
 [1, 4, 5], 
 [2, 14, 205, 44, 1], 
 [2, 14, 205, 44, 2], 
 [3, 8, 6]]

As side, another way using Comparator interface (I agree this is not very nice), it compares the value until one of the list if empty, then it will compare the size if it reaches one fully

graph.sort((o1, o2) -> {
    Comparator<List<Integer>> cc = Comparator.comparingInt(l -> l.get(0));
    int indice, min;
    for (indice = 0, min = Math.min(o1.size(), o2.size()); indice < min; indice++) {
        final int i = indice;
        cc = cc.thenComparingInt(l -> l.get(i));
    }
    return cc.thenComparingInt(List::size).compare(o1, o2);
});

Upvotes: 1

MyStackRunnethOver
MyStackRunnethOver

Reputation: 5275

So as I understand it, you want to sort the top-level list by the first element of each nested list. Is this correct? Here is how I would go about it:

List<List<Integer>> graph = new ArrayList<List<Integer>>();
// add a bunch of things ...
// ...

// Now, to sort:
graph.sort((x,y) -> Integer.compare(x.get(0), y.get(0)));

This is using Integer to get a Comparator, which is what the sort() method requires to sort by some custom criteria. In this case, we are telling it to sort the List of Lists graph by comparing two arbitrary items in graph by getting their first items and comparing them as you normally compare Integers.

Note that this assumes all items in graph have a first item.

Upvotes: 5

Related Questions