Sort a list of lists using comparator

Question

I am looking at sorting out a list of lists (on ArrayLists), using a comparator. Where the order is largest first. All sublists will always be of the same size.

For example, a list of

[[4,5,6], [7,9,10], [4,7,8], [1,2,3], [7,9,12]]

This should

[[7,9,12], [7,9,10], [4,7,8], [4,5,6], [1,2,3]]

I have something like this but only sorts by the first item in each list

List<List<Integer>> list = Arrays.asList(
                Arrays.asList(4,5,6),
                Arrays.asList(7,9,10), 
                Arrays.asList(4,7,8),
                Arrays.asList(1,2,3), 
                Arrays.asList(7,9,12));

list.sort((l1, l2) -> l2.get(0).compareTo(l1.get(0)));

Which produces:

[[7, 9, 10], [7, 9, 12], [4, 5, 6], [4, 7, 8], [1, 2, 3]]

How can I write a comparator, which sorts by the next item in the list if the item before is equal?

For example, [7, 9, 10], [7, 9, 12] should go onto compare the two 7, then the two 9 and then 10 and 12. For example, [4, 5, 6], [4, 7, 8] should go onto compare the two 4, and tthen the 4 and 7 and stop.

Answer 1

You can define a comparator as such:

Comparator<List<Integer>> comparator = (list1, list2) -> {
       for (int i = 0; i < list1.size(); i++) {
            int value = Integer.compare(list2.get(i), list1.get(i));
            if (value != 0)
                return value;
       }
       return 0;
};

or:

Comparator<List<Integer>> comparator = (list1, list2) -> 
IntStream.range(0, list1.size())
         .map(i -> Integer.compare(list2.get(i), list1.get(i)))
         .filter(value -> value != 0)
         .findFirst()
         .orElse(0);

Then sort:

list.sort(comparator);

Update:

You can further generalise this by creating a custom generic function that returns a comparator i.e.:

static <T extends Comparable<T>> Comparator<List<T>> comparator(){
       return (o1, o2) -> IntStream.range(0, o1.size())
                                   .map(i -> o2.get(i).compareTo(o1.get(i)))
                                   .filter(value -> value != 0)
                                   .findFirst()
                                   .orElse(0);
}

Now you can do:

List<List<Integer>> integerList = Arrays.asList(
                Arrays.asList(4,5,6),
                Arrays.asList(7,9,10),
                Arrays.asList(4,7,8),
                Arrays.asList(1,2,3),
                Arrays.asList(7,9,12));

integerList.sort(comparator()); // sort list of integers descending

List<List<String>> stringList = Arrays.asList(
                Arrays.asList("a","b","c"),
                Arrays.asList("d","e","f"),
                Arrays.asList("g","h","i"));

stringList.sort(comparator()); // sort list of strings descending 

and so forth...

Note - I am using JDK 9+ so I don't know if the type inference is good enough in versions prior to JDK 8.

Answer 2

The sorting order that you are trying to achieve is called Lexicographical order.

In order to compare two lists with this order, you can simply walk through the lists, and compare the corresponding elements. As soon as one comparison yields a non-zero value, this value can be returned. If all elements are equal, zero is returned.

So you can implement the core of this comparison with a generic method:

private static <T> int compareLexicographically(
    List<? extends T> list0,
    List<? extends T> list1, 
    Comparator<? super T> comparator)

Based on this method, you can assemble different sorts of comparators. For Integer values (and other types that implement the Comparable interface), you can use the Comparator#naturalOrder comparator as the last argument. For other types, you can feed in a different comparator. You also always have the option to create a reversed comparator from that, for example.

Here is an example showing how such a method can be implemented and used for sorting Integer objects, String objects, or custom objects (here, a simple Person class, which is compared by their getName).

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class LexicographicalComparator
{
    public static void main(String[] args)
    {
        exampleWithIntegers();
        exampleWithStrings();
        exampleWithPersons();
    }

    private static void exampleWithIntegers()
    {
        List<List<Integer>> list = Arrays.asList(
            Arrays.asList(4, 5, 6), 
            Arrays.asList(7, 9, 10),
            Arrays.asList(4, 7, 8), 
            Arrays.asList(1, 2, 3),
            Arrays.asList(7, 9, 12));

        Comparator<List<Integer>> comparator = lexicographicalComparator();
        list.sort(comparator.reversed());

        System.out.println("Integers, descending:");
        list.forEach(System.out::println);
    }

    private static void exampleWithStrings()
    {
        List<List<String>> list = Arrays.asList(
            Arrays.asList("B", "B", "C"), 
            Arrays.asList("C", "B", "B"),
            Arrays.asList("B", "C", "A"), 
            Arrays.asList("A", "C", "B"),
            Arrays.asList("C", "B", "A"));

        Comparator<List<String>> comparator = lexicographicalComparator();
        list.sort(comparator);

        System.out.println("Strings, ascending:");
        list.forEach(System.out::println);
    }

    private static void exampleWithPersons()
    {
        class Person 
        {
            String name;
            Person(String name)
            {
                this.name = name;
            }
            String getName()
            {
                return name;
            }

            @Override
            public java.lang.String toString()
            {
                return name;
            }
        }

        List<List<Person>> list = Arrays.asList(
            Arrays.asList(new Person("B"), new Person("B"), new Person("C")), 
            Arrays.asList(new Person("C"), new Person("B"), new Person("B")),
            Arrays.asList(new Person("B"), new Person("C"), new Person("A")), 
            Arrays.asList(new Person("A"), new Person("C"), new Person("B")),
            Arrays.asList(new Person("C"), new Person("B"), new Person("A")));

        Comparator<List<Person>> comparator = 
            lexicographicalComparator(Comparator.comparing(Person::getName));
        list.sort(comparator);

        System.out.println("Persons, by name, ascending:");
        list.forEach(System.out::println);
    }



    private static <T extends Comparable<? super T>> Comparator<List<T>> 
        lexicographicalComparator()
    {
        return (list0, list1) -> 
            compareLexicographically(list0, list1, Comparator.naturalOrder());
    }

    private static <T> Comparator<List<T>> lexicographicalComparator(
        Comparator<? super T> comparator)
    {
        return (list0, list1) -> 
            compareLexicographically(list0, list1, comparator);
    }

    private static <T> int compareLexicographically(
        List<? extends T> list0,
        List<? extends T> list1, 
        Comparator<? super T> comparator)
    {
        if (list0.size() < list1.size())
        {
            return -1;
        }
        if (list0.size() > list1.size())
        {
            return 1;
        }
        for (int i = 0; i < list0.size(); i++)
        {
            T t0 = list0.get(i);
            T t1 = list1.get(i);
            int value = comparator.compare(t0, t1);
            if (value != 0)
            {
                return value;
            }
        }
        return 0;
    }
}

You may still have to think about corner cases. The most important ones are:

• What happens when the lists have different sizes?
• What happens when the lists contain null elements?

The first one is currently handled by basically first sorting the lists by their size, which may or may not be what you want.

The latter can easily be handled by passing a Comparator#nullsFirst or Comparator#nullsLast comparator to the outer method, but you have to be aware of that.