Как сортировать с помощью компаратора java
Перейти к содержимому

Как сортировать с помощью компаратора java

  • автор:

Как сортировать с помощью компаратора java

В прошлой теме была рассмотрена работа коллекции TreeSet, типизированной объектами String. При добавлении новых элементов объект TreeSet автоматически проводит сортировку, помещая новый объект на правильное для него место. Однако со строками все понятно. А что если бы мы использовали не строки, а свои классы, например, следующий класс Person:

class Person < private String name; Person(String name)< this.name=name; >String getName() >

Объект TreeSet мы не сможем типизировать данным классом, поскольку в случае добавления объектов TreeSet не будет знать, как их сравнивать, и следующий кусок кода не будет работать:

TreeSet people = new TreeSet(); people.add(new Person("Tom"));

При выполнении этого кода мы столкнемся с ошибкой, которая скажет, что объект Person не может быть преобразован к типу java.lang.Comparable.

Для того, чтобы объекты Person можно было сравнить и сортировать, они должны применять интерфейс Comparable . При применении интерфейса он типизируется текущим классом. Применим его к классу Person:

class Person implements Comparable < private String name; Person(String name)< this.name = name; >String getName() public int compareTo(Person p) < return name.compareTo(p.getName()); >>

Интерфейс Comparable содержит один единственный метод int compareTo(E item) , который сравнивает текущий объект с объектом, переданным в качестве параметра. Если этот метод возвращает отрицательное число, то текущий объект будет располагаться перед тем, который передается через параметр. Если метод вернет положительное число, то, наоборот, после второго объекта. Если метод возвратит ноль, значит, оба объекта равны.

В данном случае мы не возвращаем явным образом никакое число, а полагаемся на встроенный механизм сравнения, который есть у класса String. Но мы также можем определить и свою логику, например, сравнивать по длине имени:

public int compareTo(Person p)

Теперь мы можем типизировать TreeSet типом Person и добавлять в дерево соответствующие объекты:

TreeSet people = new TreeSet(); people.add(new Person("Tom"));

Интерфейс Comparator

Однако перед нами может возникнуть проблема, что если разработчик не реализовал в своем классе, который мы хотим использовать, интерфейс Comparable, либо реализовал, но нас не устраивает его функциональность, и мы хотим ее переопределить? На этот случай есть еще более гибкий способ, предполагающий применение интерфейса Comparator.

Интерфейс Comparator содержит ряд методов, ключевым из которых является метод compare() :

public interface Comparator  < int compare(T a, T b); // остальные методы >

Метод compare также возвращает числовое значение — если оно отрицательное, то объект a предшествует объекту b, иначе — наоборот. А если метод возвращает ноль, то объекты равны. Для применения интерфейса нам вначале надо создать класс компаратора, который реализует этот интерфейс:

class PersonComparator implements Comparator < public int compare(Person a, Person b)< return a.getName().compareTo(b.getName()); >>

Здесь опять же проводим сравнение по строкам. Теперь используем класс компаратора для создания объекта TreeSet:

PersonComparator pcomp = new PersonComparator(); TreeSet people = new TreeSet(pcomp); people.add(new Person(«Tom»)); people.add(new Person(«Nick»)); people.add(new Person(«Alice»)); people.add(new Person(«Bill»)); for(Person p : people)

Для создания TreeSet здесь используется одна из версий конструктора, которая в качестве параметра принимает компаратор. Теперь вне зависимости от того, реализован ли в классе Person интерфейс Comparable, логика сравнения и сортировки будет использоваться та, которая определена в классе компаратора.

Сортировка по нескольким критериям

Начиная с JDK 8 в механизм работы компараторов были внесены некоторые дополнения. В частности, теперь мы можем применять сразу несколько компараторов по принципу приоритета. Например, изменим класс Person следующим образом:

class Person < private String name; private int age; public Person(String n, int a)< name=n; age=a; >String getName() int getAge() >

Здесь добавлено поле для хранения возраста пользователя. И, допустим, нам надо отсортировать пользователей по имени и по возрасту. Для этого определим два компаратора:

class PersonNameComparator implements Comparator < public int compare(Person a, Person b)< return a.getName().compareTo(b.getName()); >> class PersonAgeComparator implements Comparator < public int compare(Person a, Person b)< if(a.getAge()>b.getAge()) return 1; else if(a.getAge() < b.getAge()) return -1; else return 0; >>

Интерфейс компаратора определяет специальный метод по умолчанию thenComparing , который позволяет использовать цепочки компараторов для сортировки набора:

Comparator pcomp = new PersonNameComparator().thenComparing(new PersonAgeComparator()); TreeSet people = new TreeSet(pcomp); people.add(new Person(«Tom», 23)); people.add(new Person(«Nick»,34)); people.add(new Person(«Tom»,10)); people.add(new Person(«Bill»,14)); for(Person p : people)

Bill 14 Nick 34 Tom 10 Tom 23

В данном случае сначала применяется сортировка по имени, а потом по возрасту.

Динамический компаратор для объектов с помощью ComparatorChain

Добрый день, пишет потенциальный Java разработчик. Недавно столкнулся со следующей стандартной задачей: написать многоступенчатый компаратор для сортировки коллекции простых объектов.

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

Итак обо всем по порядку. Есть некоторый класс Product:

import java.util.Formatter; import lombok.Getter; import lombok.Setter; @Setter @Getter public class Product < private String name; private Integer rate; private Double price; public Product(String name, Integer rate, Double price) < this.name = name; this.rate = rate; this.price = price; >@Override public String toString() < String shortName = name.substring(0, Math.min(name.length(), 18)); return new Formatter().format("name: %-20s rate: %8d price: %8.2f", shortName, rate, price) .toString(); >>

Если заранее известно направление (ASC, DESC) и очередность сортировки, то решение этой задачи может легко осуществиться следующим методом:

 public static List sortMethod(List products)

Аналогичные действия можно выполнить с помощью CompareToBuilder.class или других мне пока не известных библиотек.

Но как быть, если состав полей класса неизвестен заранее, а параметры сортировки хранятся в отдельном файле, и тоже могут быть заданы произвольно? Как написать динамический компаратор, способный работать без изменения кода, при изменении полей самой сущности и параметров сортировки.

Имеем класс Product, представленный выше, и параметры компаратора, которые содержатся в XML файле вида:

 asc asc desc 

Первое, что необходимо сделать — это распарсить данный файл и записать параметры нашего будущего компаратора в некую структуру, которая позволит хранить порядок записанных в нее данных. Я использовал для этого LinkedHashMap, где SortType это Enum вида:

package org.example.sort; import lombok.Getter; public enum SortType < ASC(1), DESC(-1); @Getter private int value; SortType(int i) < this.value = i; >>

Мои XMLParser.class выглядит следующим образом, возможно не самым лучшим и оптимальным, но не это является главным в данной статье. Обращаю внимание, что в качестве параметров метода getSortTypeMap() используется наш Product.class и некоторый путь к файлу с параметрами сортировки, что позволяет говорить о динамическом построении аргументов метода getComparatorBySortMap() будущего ComparatorFactory.class.

import java.io.IOException; import java.lang.reflect.Field; import java.util.LinkedHashMap; import java.util.List; import javax.xml.parsers.DocumentBuilder; import javax.xml.parsers.DocumentBuilderFactory; import javax.xml.parsers.ParserConfigurationException; import javax.xml.xpath.XPath; import javax.xml.xpath.XPathConstants; import javax.xml.xpath.XPathExpression; import javax.xml.xpath.XPathFactory; import lombok.SneakyThrows; import org.w3c.dom.Document; import org.w3c.dom.Node; import org.w3c.dom.NodeList; import org.xml.sax.SAXException; public class XMLParser < @SneakyThrows public static LinkedHashMapgetSortTypeMap (Class clazz, String path) < LinkedHashMapsortTypeMap = new LinkedHashMap<>(); List fields = List.of(clazz.getDeclaredFields()); DocumentBuilder documentBuilder; Document document = null; try < documentBuilder = DocumentBuilderFactory.newInstance().newDocumentBuilder(); document = documentBuilder.parse(path); >catch (SAXException | ParserConfigurationException | IOException e) < e.printStackTrace(); >XPathFactory pathFactory = XPathFactory.newInstance(); XPath xpath = pathFactory.newXPath(); XPathExpression expr = xpath.compile("//sort/child::*"); NodeList nodes = (NodeList) expr.evaluate(document, XPathConstants.NODESET); for (int i = 0; i < nodes.getLength(); i++) < Node n = nodes.item(i); Field field = fields.stream().filter(t ->t.getName().equals(n.getNodeName())) .findFirst() .orElse(null); if (field != null) < if (n.getTextContent().toUpperCase().equals(SortType.ASC.toString())) < sortTypeMap.put(field, SortType.ASC); >if (n.getTextContent().toUpperCase().equals(SortType.DESC.toString())) < sortTypeMap.put(field, SortType.DESC); >> > return sortTypeMap; > >

И теперь непосредственно сам класс, позволяющий сгенерировать необходимый компаратор и основанный на использовании ComparatorChain.class и BeanComparator.class:

import java.lang.reflect.Field; import java.util.LinkedHashMap; import java.util.Map; import org.apache.commons.beanutils.BeanComparator; import org.apache.commons.collections4.comparators.ComparatorChain; public class ComparatorFactory  < public ComparatorChaingetProductComparatorBySortMap( LinkedHashMap sortTypeMap) < if (sortTypeMap.isEmpty()) < return null; >ComparatorChain chain = new ComparatorChain<>(); String parameterName; boolean direction; for (Map.Entry sortParametr : sortTypeMap.entrySet()) < parameterName = sortParametr.getKey().getName(); direction = sortParametr.getValue().getValue() (parameterName), direction); > return chain; > >

В результате мы получаем возможность генерировать компараторы на основе данных о классе и порядке сортировки, при этом и класс, и порядок могут изменяться.

Заранее прошу прощения за возможные огрехи в коде и отсутствие более глубокого анализа скорости работы такого метода, возможных ошибках и недостатках, которые не смог отразить в статье в силу отсутствия опыта в коммерческом программировании.

Буду рад комментариям под моей первой статьей.

Компаратора сортировка по убыванию

Подскажите, пожалуйста, как с помощью компаратора вывести учеников с их оценками по убыванию.

1 2 3 4 5 6
package lab6_2; public interface ComparableT>{ int compareTo(Students y1, Students y2); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
package lab6_2; public class Students implements Comparable Students>{ int grade; String name; public Students(String name,int grade){ this.grade = grade; this.name = name; } @Override public int compareTo(Students y1, Students y2) { return y1.grade > y2.grade ? -1 :(y1.grade  y2.grade ? 1 : 0); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
package lab6_2; import java.util.ArrayList; import java.util.Collections; public class TestStudents { public static void main(String[] args) { // write your code here ArrayListStudents> myStudentsArrayList = new ArrayListStudents>(); Students x1 = new Students("Bill", 5); Students x2 = new Students("Anna", 2); Students x3 = new Students("Max", 3); Students x4 = new Students("Billy", 4); Students x5 = new Students("Nik", 5); myStudentsArrayList.add(x1); myStudentsArrayList.add(x2); myStudentsArrayList.add(x3); myStudentsArrayList.add(x4); myStudentsArrayList.add(x5); //Collections.sort(myStudentsArrayList, new Students()); for(Students i : myStudentsArrayList){ System.out.println(i.name + " " + i.grade ); } } }

Сортировка списков в Java

Для возможности сортировки объектов в коллекциях наследниках List в Java существует статический метод класса java.util.Collections .

Это значит вы можете сортировать элементы таких классов как ArrayList, LinkedList, CopyOnWriteArrayList и других классов, имплементирующих интерфейс List .

В общем виде, если у вас есть список из строк:

[z, b, c, a, k, z] 

то после сортировки получите в списке порядок:

[a, b, c, k, z, z] 

Простое использование метода sort() #

Если у нас в списке находятся объекты классов, которые известно как сравнить, то достаточно просто вызвать метод sort() и передать туда список. Таким образом в списке элементы поменяют порядок и будут отсортированы в порядке возрастания

//создание списка на основе массива  var stringList = Arrays.asList("z", "b", "c", "a", "k", "z"); System.out.println(stringList);  //сортировка списка в порядке возрастания  Collections.sort(stringList);  System.out.println(stringList); 

Вывод в консоль:

[z, b, c, a, k, z] [a, b, c, k, z, z] 

Так мы можем сортировать множество стандартных классов, таких как String, Integer, Double, Character и множество других.

Если более точно выразиться, то без дополнительных параметров возможно отсортировать список из любых элементов, классы которых имплементируют интерфейс сравнения Comparable .

Сортировка в обратном порядке #

Если мы хотим сортировать элементы в обратном порядке. То для этого передадим дополнительный аргумент в метод сортировки:

//создание списка на основе массива  var stringList = Arrays.asList("z", "b", "c", "a", "k", "z"); System.out.println(stringList);  //сортировка списка в обратном направлении  Collections.sort(stringList, Collections.reverseOrder());  System.out.println(stringList); 
[z, b, c, a, k, z] [z, z, k, c, b, a] 

Добавляем возможность сортировки своих классов #

Если стандартные классы уже готовы к сортировке, то если мы напишем свой класс, то Java не знает как есть сравнивать с объектами этого же класса.

Чтобы научить сравнивать объекты есть два варианта:

  • создать класс на основе Comparator и там прописать правила сравнения в методе int compare(T o1, T o2) . Полученный объект из класса использовать всегда, когда нам надо сортировать объекты. Такой вариант отлично подходит, когда нам надо сортировать объекты по разным правилам и можем использовать нужный нам класс Comparator.
  • добавить в класс (являющимся, элементом списка) имплементацию интерфейса Comparable и прописать правила сравнения в методе int compareTo(T o) . Тогда не потребуется указывать каждый раз компаратор, данное правило сравнение будет по-умолчанию для этого объекта.

Оба метода возвращают целое число, которое обычно интерпретируется так:

  • число больше 0 -> объект с которым сравнивают больше текущего
  • число равно 0 -> объекты одинаковые
  • число меньше 0 -> объект с которым сравнивают меньше текущего

Создадим свой класс, например для студента:

class Student   private final String name;  private final double avgMark;   public Student(String name, double avgMark)   this.name = name;  this.avgMark = avgMark;  >   @Override  public String toString()   return " + name + '\'' + ", m=" + avgMark + '>';  > > 

Класс специально минимально простой: все параметры задаются в конструкторе, и используются значения только для печати данных при вызове toString, что поможет нам в визуализации результата.

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

var ivan = new Student("Иван", 4.3); var olga = new Student("Ольга", 3.8); var eugene = new Student("Женя", 4.9); var studentList = Arrays.asList(ivan, olga, eugene);  System.out.println(studentList); //сортировка списка  Collections.sort(studentList); System.out.println(studentList); 

Такой код не скомпилируется, так как метод sort() не просто ожидает список, но еще важно, чтобы элемент списка был наследником Comparable:

public static T extends Comparable super T>> void sort(ListT> list)   list.sort(null); > 

Использование Comparable #

Для создания возможности сортировки, нам необходимо научить сравнить объекты с другими такого-же типа. И такая реализация будет использоваться по-умолчанию при сравнении объектов одного класса.

Имплементируем Comparable интерфейс, и реализуем метод compareTo:

class Student implements ComparableStudent>   private final String name;  private final double avgMark;   public Student(String name, double avgMark)   this.name = name;  this.avgMark = avgMark;  >   @Override  public String toString()   return " + name + '\'' + ", m=" + avgMark + '>';  >   @Override  public int compareTo(Student o)   return name.compareTo(o.name);  > > 

Обратите внимание, внутри метод мы решили сравнить две строки, а так как у String есть реализация Comparable — мы можем ее использовать.

В данном коде опущены части, с проверкой на null объектов o и полей класса.

Давайте проверим, как это будет работать:

var ivan = new Student("Иван", 4.3); var olga = new Student("Ольга", 3.8); var eugene = new Student("Женя", 4.9);  var studentList = Arrays.asList(ivan, olga, eugene); System.out.println(studentList); //сортировка списка  Collections.sort(studentList); System.out.println(studentList); 

Все отлично, список отсортирован по полю name .

Вы можете делать более сложные условия сравнения, только не забывайте учитывать требование для успешной сортировки — два объекта, сколько бы мы их не сравнивали — должны всегда давать одинаковый результат.

Использование Comparator #

А что если нам надо сортировать студентов не по имени, а по средней оценке? И при этом оставить возможность сортировать по имени, которое должна использоваться по умолчанию для создания различных документов.

Нам на помощь придет отдельный класс Comparator , которые хранит в себе логику сравнения объектов и при сортировке, мы можем использовать нужное правило, то есть нужный объект класса Comparator .

Для начала добавим в класс Student геттеры, так как нам уже необходимо использовать данные класса в классе компаратора.

class Student implements ComparableStudent>   private final String name;  private final double avgMark;   public Student(String name, double avgMark)   this.name = name;  this.avgMark = avgMark;  >   @Override  public String toString()   return " + name + '\'' + ", m=" + avgMark + '>';  >   @Override  public int compareTo(Student o)   return name.compareTo(o.name);  >   public String getName()   return name;  >   public double getAvgMark()   return avgMark;  > > 

и теперь создадим класс Comparator , тип для сравнения Student :

class ComparatorByAvgMark implements ComparatorStudent>   @Override  public int compare(Student o1, Student o2)   return Double.compare(o1.getAvgMark(), o2.getAvgMark());  > > 

Мы снова использовали готовый метод для сравнения стандартного класса Double , это помогает не выдумывать свои реализации, а использовать уже существующие.

Также снова опущены проверки на null объектов o1, o2.

Теперь можно использовать данный класс, и в этот раз нам пригодится перегруженный метод Collections.sort() , который принимает компаратор:

var ivan = new Student("Иван", 4.3); var olga = new Student("Ольга", 3.8); var eugene = new Student("Женя", 4.9);  var studentList = Arrays.asList(ivan, olga, eugene); System.out.println(studentList);  //сортировка списка c использованием компаратора  Collections.sort(studentList, new ComparatorByAvgMark());  System.out.println(studentList); 

И мы видим — сортировка по возрастанию средней оценки студента.

Хорошо, давайте сделаем обратную сортировку, высокие оценки должны быть в начале списка. Для этого нам потребуется изменить поведение компаратора, и для этого у компаратора есть метод reversed() :

Collections.sort(studentList, new ComparatorByAvgMark().reversed()); 

и в итоге получим нужный результат:

Но это еще не все что может компаратор, можно создавать цепочки. Например, сначала сортируем по оценкам, а если оценки одинаковые, то по имени.

Это можно реализовать не создавая отдельного класса, а воспользоваться функцией:

Collections.sort(studentList,  new ComparatorByAvgMark().reversed()  .thenComparing(Student::getName)); 

При такой сортировки, оценки будут в порядке убывания, а внутри одной средней оценки, студенты будут по имени в порядке возрастания.

Метод sort() у самого списка #

Кроме использования метода Collections.sort() , можно вызывать похожий метод у самого списка List.sort() . Метод принимает один аргумент — компаратор.

На примере списка студентов:

studentList.sort(new ComparatorByAvgMark()); 

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *