Порядок при сортировке списка с помощью компаратора

333
28 января 2017, 09:39

Имеем такой тестовый код. Предполагается, что созданные классы должны отсортироваться в первом случае (LegComparator) по наибольшему количеству ног, а во втором случае (TailComparator) по наличию хвостов.

В обоих случаях вывод (как я думал) должен быть: сначала собаки, а потом киви.

Однако получается все наоборот. Какую важную вещь я упустил?

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Test {
    public static void main(String[] args) {
        ArrayList<Animal> any = new ArrayList<>();
        any.add(new Kiwi());
        any.add(new Dog());
        any.add(new Kiwi());
        any.add(new Dog());
        Collections.sort(any, new LegComparator());
        for (Animal animal : any) {
            System.out.println(animal);
        }
        System.out.println();
        Collections.sort(any, new TailComparator());
        for (Animal animal : any) {
            System.out.println(animal);
        }
    }
    static class Animal {
        protected int     countLeg = 2;
        protected boolean tail     = false;
    }
    static class Dog extends Animal {
        public Dog() {
            countLeg = 4;
            tail = true;
        }
        @Override
        public String toString() {
            return "Dog";
        }
    }
    static class Kiwi extends Animal {
        public Kiwi() {
        }
        @Override
        public String toString() {
            return "Kiwi";
        }
    }
    static class LegComparator implements Comparator<Animal> {
        @Override
        public int compare(Animal first, Animal second) {
            if (first.countLeg == second.countLeg) {
                return 0;
            }
            return first.countLeg > second.countLeg ? 1 : -1;
        }
    }
    static class TailComparator implements Comparator<Animal> {
        @Override
        public int compare(Animal first, Animal second) {
            if ((first.tail && second.tail) || !(first.tail && second.tail)) {
                return 0;
            }
            return first.tail ? 1 : -1;
        }
    }
}
Answer 1

... в обоих случаях вывод (как я думал) должен быть - сначала собаки, а потом киви ...

Все методы, выполняющие сортировку сортируют по возрастанию. Т.е. сначала пойдут существа с меньшим числом ног (киви) затем с большим (собаки).

С точки зрения контракта Comparator это означает, что в отсортированном списке для индексов i, j таких, что i < j верно, что comparator(a.get(i), a.get(j)) <=0

Подробнее об этом можно почитать в документации Collections.sort и Comparator.

P.S. TailComparator работает некорректно, т.к. выражение (first.tail && second.tail) || !(first.tail && second.tail) всегда true. Последовательность выводится в правильном порядке только потому, что алгоритм сортировки не меняет порядок элементов если не может корректно определить порядок. Если вы закомментируете первую сортировку, вторая перестанет работать.

Метод compare для хвостов можно реализовать, например, так:

public int compare(Animal first, Animal second) {
    return ((Boolean) first.tail).compareTo(second.tail);
}
Answer 2

Сортировка происходит по "возрастанию". При этом считается, что один элемент (first) "больше" другого (second), если compare(first, second) возвращает 1.

Есть как минимум три варианта как изменить порядок элементов, чтобы собаки были до киви:

  1. Заменить

    return first.countLeg > second.countLeg ? 1 : -1;

    На

    return first.countLeg > second.countLeg ? -1 : 1;

    Однако этот вариант не подойдёт, если вам нужно использовать этот компаратор и для сортировки в другом направлении.

  2. Использовать Collections.reverseOrder для сортировки в обратном для данного компаратора порядке:

    Collections.sort(any, Collections.reverseOrder(new LegComparator()));

    Этот метод возвращает новый компаратор (не всегда, но в данном случае создастся новый), внутри которого в compare(T t1, T t2) происходит вызов оригинального компаратора как compare(t2, t1).

  3. Можно и вовсе не трогать компаратор, а разворачивать список после сортировки:

    Collections.sort(any, new LegComparator());
    Collections.reverse(any);

Однако это требует дополнительное (хоть и линейное) время на разворот списка.

READ ALSO
Интернационализация веб-приложения

Интернационализация веб-приложения

В spring'e использую для решения CookieLocaleResolver, LocaleChangeInterceptor и ReloadableResourceBundleMessageSourceВсе настроено согласно множеству примеров и документации, работает...

327
Подключение библиотек к проекту в NetBeans

Подключение библиотек к проекту в NetBeans

Здравствуйте! Возник ооооочень глупый вопрос, но очень прошу помочьЕсть следующий код:

619
Файл не сохраняется когда он .jar

Файл не сохраняется когда он .jar

Хотел поработать с файлами, программка работает в IntellijIdea, но когда создаюjar файл он не сохраняет изменение на файл, выдает ошибку

339
Java. Где располагается объект hash таблицы для HashMap?

Java. Где располагается объект hash таблицы для HashMap?

Пытаюсь разобраться с устройством hash таблиц на примере взаимодействия с HashMap но никак не могу найти сам массив-таблицуГде она находится?

303