2

I am trying to sort a List<List<Integer>> lexicographical manner. But I'm unable to achieve the goal and don't get where is the issue.

List<List<Integer>> result = new ArrayList<List<Integer>>();

    result.add(Arrays.asList(1, 3, 76, 99));
    result.add(Arrays.asList(1, 2, 84, 92));
    result.add(Arrays.asList(1, 1, 76, 99));

    java.util.Collections.sort(result, (item1, item2) -> {

        if (item1.get(0) > item2.get(0) || item1.get(1) > item2.get(1) || item1.get(2) > item2.get(2)
                || item1.get(3) > item2.get(3)) {
            return 1;
        } else {
            return -1;
        }
    });

Expected output: [[1, 1, 76, 99], [1, 2, 84, 92], [1, 3, 76, 99]]

But I'm getting [[1, 3, 76, 99], [1, 2, 84, 92], [1, 1, 76, 99]]

I want that index wise smallest number will come first. In the example, all three lists have 1 at the first position, so no change. At the second position, 3rd list has 1 which is the minimum among the three so 3rd list will be moved to the first. Then considering the 2nd item of 2nd and 3rd list 2 is lower so second list will remain at the 2nd position.

Moshiur Rahman
  • 347
  • 2
  • 8
  • 1
    What do you mean by "*lexicographical order*"? Lexicographical order is defined on `String`s, not `int`s. – Turing85 Oct 20 '21 at 19:18
  • 1
    `item1.get(0) > item2.get(0) || item1.get(1) > item2.get(1)` will be true for `[[0, 2], [1, 1]]` because the second half is true. Also, you're missing an equal (0) path. – shmosel Oct 20 '21 at 19:18
  • If the input is backwards, do you want to flip `-1` and `1`? What if all the numbers are the same? Should you return `0`? Do you have a better example? – OneCricketeer Oct 20 '21 at 19:18
  • 1
    @Turing85 You can apply lexicographical ordering to any sequence of ordered elements. See for example Guava's [`Ordering.lexicographical()`](https://guava.dev/releases/23.0/api/docs/com/google/common/collect/Ordering.html#lexicographical--). – shmosel Oct 20 '21 at 19:21
  • I want that index wise smallest number will come first. In the example, all three lists have 1 at the first position, so no change. At the second position, 3rd list has 1 which is the minimum among the three so 3rd list will be moved to the first. Then considering the 2nd item of 2nd and 3rd list 2 is lower so second list will remain at the 2nd position. – Moshiur Rahman Oct 20 '21 at 19:25
  • The problem is that you aren't checking whether prior elements are equal or not. Short circuiting should only apply if they are. – Mad Physicist Oct 20 '21 at 19:26
  • For each pair of elements, you must check whether the first is less than the other, and you must check whether they are equal. It is not sufficient to only check whether the first value is greater than the second value. – VGR Oct 20 '21 at 19:36

3 Answers3

5

The condition you have is wrong. When item1.get(0) < item2.get(0) you simply continue your short-circuited comparison instead of returning -1. Also, any time you have a comparator that does not return 0, I get automatically suspicious.

A simple fix would be to use a loop:

for(int i = 0; i < 4; i++) {
    int i1 = item1.get(i);
    int i2 = item2.get(i);
    if(i1 < i2) {
        return -1;
    } else if(i1 > i2) {
        return 1;
    }
}
return 0;

You could simplify the loop to

for(int i = 0; i < 4; i++) {
    int d = item1.get(i) - item2.get(i);
    if(d != 0) {
        return d;
    }
}
return 0;
Mad Physicist
  • 107,652
  • 25
  • 181
  • 264
2

You can do it in a generic way, based on MatinS answer:

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<>());
Benjamin RD
  • 11,516
  • 14
  • 87
  • 157
  • Why `Integer.compare(o1.size(), o2.size());` instead of `o1.size() - o2.size()`? You end up performing a whole bunch of unnecessary boxing/unboxing. – Mad Physicist Oct 20 '21 at 19:42
  • Also, thanks for finding the duplicate. The correct response here would be to mark the question for closure. – Mad Physicist Oct 20 '21 at 19:43
  • 1
    @MadPhysicist [`Integer::compare`](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Integer.html#compare(int,int)) takes two `int`s as parameters, so no boxing is performed. The algorithm - as written - performs 0 (un)boxing operations. – Turing85 Oct 20 '21 at 20:03
  • In that case, it's more flexible than the one I've got. BTW, you need `compare` to avoid catastrophic corner cases where the difference doesn't fit into an integer. Since size >= 0 always, a simple difference is guaranteed to suffice – Mad Physicist Oct 20 '21 at 20:09
1

Building off of Mad Physicist's answer, here is a more general solution and usage:

public final class SortingListOfListExample {

  public static void main(final String[] args) {
    final List<List<Integer>> result = new ArrayList<>();

    result.add(List.of(1, 3, 76, 99));
    result.add(List.of(1, 2, 84, 92));
    result.add(List.of(1, 1, 76, 99));

    System.out.println(result);

    result.sort(new ListComparator<>());

    System.out.println(result);
  }

  private static final class ListComparator<T extends Comparable<T>> implements Comparator<List<T>> {

    @Override
    public final int compare(final List<T> list1, final List<T> list2) {
      final int minSize = Math.min(list1.size(), list2.size());

      for(int i = 0; i < minSize; i++) {
        // Be wary of nulls.
        final int compareResult = list1.get(i).compareTo(list2.get(i));

        if(compareResult != 0) {
          return compareResult;
        }
      }

      return Integer.compare(list1.size(), list2.size());
    }

  }

}
Oliver
  • 1,465
  • 4
  • 17