26

How would I sort a list of lists in Java in lexicographical order using Collections.sort() or another sorting method?

private List<List<Integer>> possiblePoles = setPoles();    
System.out.println(possiblePoles)
[[1, 3, 5], [1, 2, 3]]

5 Answers5

36

You will have to implement your own Comparator class and pass in an instance to Collections.sort()

class ListComparator<T extends Comparable<T>> implements Comparator<List<T>> {

  @Override
  public int compare(List<T> o1, List<T> o2) {
    for (int i = 0; i < Math.min(o1.size(), o2.size()); i++) {
      int c = o1.get(i).compareTo(o2.get(i));
      if (c != 0) {
        return c;
      }
    }
    return Integer.compare(o1.size(), o2.size());
  }

}

Then sorting is easy

List<List<Integer>> listOfLists = ...;

Collections.sort(listOfLists, new ListComparator<>());
MartinS
  • 2,759
  • 1
  • 15
  • 25
  • Even better: Because Java uses type erasure, you can make a singleton instance of ListComparator and do unsafe casts (it's stateless anyway). – Nayuki Mar 03 '16 at 02:33
  • @Nayuki, I'd rather not do that because I do not want to carry around the instance forever, just because I used it once. The memory footprint might be tiny but so is the cost of creating an object. But everyone can do whatever they want ^^ – MartinS Mar 03 '16 at 02:49
  • 1
    I'd use `int c = ObjectUtils.compare(o1.get(i), o2.get(i))`. Otherwise you get a NPE if `o1.get(i)==null`. (`ObjectUtils` is from the apache commons library) – Michael Anderson May 26 '17 at 00:40
  • Special case: If the lists are long linked lists, accessing by index is inefficient. In this case one should prefer to use two iterators. – Ole V.V. Feb 09 '20 at 13:38
7

Improved MartinS answer using Java 8 stream API

possiblePoles = possiblePoles.stream().sorted((o1,o2) -> {
             for (int i = 0; i < Math.min(o1.size(), o2.size()); i++) {
                  int c = o1.get(i).compareTo(o2.get(i));
                  if (c != 0) {
                    return c;
                  }
                }
                return Integer.compare(o1.size(), o2.size());
         }).collect(Collectors.toList());
Joby Wilson Mathews
  • 10,528
  • 6
  • 54
  • 53
1

For this example [[1, 3], [1, 2]], if you want to sort the list by both elements you can use sorted from Java 8 manually implemented the comparator method, validating all cases like the following example:

List<List<Integer>> result = contests.stream().sorted((o1, o2) -> {
        if (o1.get(1) > o2.get(1) ||
            (o1.get(1).equals(o2.get(1)) && o1.get(0) > o2.get(0))) {
            return -1;
        } else if (o1.get(1) < o2.get(1) ||
            (o1.get(1).equals(o2.get(1)) && o1.get(0) < o2.get(0))) {
            return 1;
        }
        return 0;
    }).collect(Collectors.toList());

OR

contests.sort((o1, o2) -> {
                if (o1.get(1) > o2.get(1) ||
                    (o1.get(1).equals(o2.get(1)) && o1.get(0) > o2.get(0))) {
                    return -1;
                } else if (o1.get(1) < o2.get(1) ||
                    (o1.get(1).equals(o2.get(1)) && o1.get(0) < o2.get(0))) {
                    return 1;
                }
                return 0;
            });
Camilo
  • 31
  • 3
0
  possiblePoles.sort((l1, l2) -> {
        int minLength = Math.min(l1.size(), l2.size());
        for (int i = 0; i < minLength; i++) {
            int lexicographicalPosition = l1.get(i).compareTo(l2.get(i));
            if (lexicographicalPosition != 0) {
                return lexicographicalPosition;
            }
        }
        return Integer.compare(l1.size(), l2.size());
    });

Same logic with java 8

Chaman Jain
  • 71
  • 1
  • 2
0

Try Using this code.

Collections.sort(list, (a,b) -> a.get(0) - b.get(0));

R..V
  • 1
  • 1