Tri avec Comparable et Comparator en Java

Les programmeurs ont souvent besoin de trier les éléments d'une base de données dans une collection, un tableau ou une carte. En Java, nous pouvons implémenter n'importe quel algorithme de tri que nous voulons avec n'importe quel type. En utilisant l' Comparableinterface et la compareTo()méthode, nous pouvons trier en utilisant l'ordre alphabétique, la Stringlongueur, l'ordre alphabétique inversé ou les nombres. L' Comparatorinterface nous permet de faire de même mais de manière plus flexible.

Quoi que nous voulions faire, nous avons juste besoin de savoir comment implémenter la logique de tri correcte pour l'interface et le type donnés.

Obtenez le code source

Obtenez le code de ce Java Challenger. Vous pouvez exécuter vos propres tests tout en suivant les exemples.

Tri d'une liste Java avec un objet personnalisé

Pour notre exemple, nous utiliserons le même POJO que nous avons utilisé pour d'autres challengers Java jusqu'à présent. Dans ce premier exemple, nous implémentons l'interface Comparable dans la Simpsonclasse, en utilisant Simpsondans le type générique:

 class Simpson implements Comparable { String name; Simpson(String name) { this.name = name; } @Override public int compareTo(Simpson simpson) { return this.name.compareTo(simpson.name); } } public class SimpsonSorting { public static void main(String... sortingWithList) { List simpsons = new ArrayList(); simpsons.add(new SimpsonCharacter("Homer ")); simpsons.add(new SimpsonCharacter("Marge ")); simpsons.add(new SimpsonCharacter("Bart ")); simpsons.add(new SimpsonCharacter("Lisa ")); Collections.sort(simpsons); simpsons.stream().map(s -> s.name).forEach(System.out::print); Collections.reverse(simpsons); simpsons.stream().forEach(System.out::print); } } 

Notez que nous avons remplacé la méthode compareTo () et passé un autre Simpsonobjet. Nous avons également remplacé la toString()méthode, juste pour rendre l'exemple plus facile à lire.

La toStringméthode affiche toutes les informations de l'objet. Lorsque nous imprimons l'objet, la sortie sera celle qui a été implémentée dans toString().

La méthode compareTo ()

La compareTo()méthode compare un objet donné ou l'instance actuelle avec un objet spécifié pour déterminer l'ordre des objets. Voici un aperçu rapide de son compareTo()fonctionnement:

  Si la comparaison retourne

  Ensuite ...

  >= 1

  this.name > simpson.name

  0

  this.name == simpson.name

  <= -1

  this.name < simpson.name

Nous ne pouvons utiliser que des classes comparables à la sort()méthode. Si nous essayons de passer un Simpsonqui n'implémente pas Comparable, nous recevrons une erreur de compilation.

La sort()méthode utilise le polymorphisme en passant n'importe quel objet Comparable. Les objets seront ensuite triés comme prévu.

La sortie du code précédent serait:

 Bart Homer Lisa Marge 

Si nous voulions inverser l'ordre, nous pourrions échanger le sort()pour un reverse(); de:

 Collections.sort(simpsons); 

à:

 Collections.reverse(simpsons); 

Le déploiement de la reverse()méthode changerait la sortie précédente en:

 Marge Lisa Homer Bart 

Trier un tableau Java

En Java, nous pouvons trier un tableau avec n'importe quel type que nous voulons tant qu'il implémente l' Comparableinterface. Voici un exemple:

 public class ArraySorting { public static void main(String... moeTavern) { int[] moesPints = new int[] {9, 8, 7, 6, 1}; Arrays.sort(moesPints); Arrays.stream(moesPints).forEach(System.out::print); Simpson[] simpsons = new Simpson[]{new Simpson("Lisa"), new Simpson("Homer")}; Arrays.sort(simpsons); Arrays.stream(simpsons).forEach(System.out::println); } } 

Lors du premier sort()appel, le tableau est trié dans:

 1 6 7 8 9 

Dans le deuxième sort()appel, il est trié comme suit:

 Homer Lisa 

Gardez à l'esprit que les objets personnalisés doivent être implémentés Comparablepour être triés, même sous forme de tableau.

Puis-je trier des objets sans Comparable?

Si l'objet Simpson n'était pas implémenté Comparable, une ClassCastException serait lancée. Si vous exécutez ceci comme un test, vous verrez quelque chose comme la sortie suivante:

 Error:(16, 20) java: no suitable method found for sort(java.util.List) method java.util.Collections.sort(java.util.List) is not applicable (inference variable T has incompatible bounds equality constraints: com.javaworld.javachallengers.sortingcomparable.Simpson lower bounds: java.lang.Comparable) method java.util.Collections.sort(java.util.List,java.util.Comparator) is not applicable (cannot infer type-variable(s) T (actual and formal argument lists differ in length)) 

Ce journal peut être déroutant, mais ne vous inquiétez pas. Gardez simplement à l'esprit qu'un ClassCastExceptionsera lancé pour tout objet trié qui n'implémente pas l' Comparableinterface.

Trier une carte avec TreeMap

L'API Java comprend de nombreuses classes pour faciliter le tri, notamment TreeMap. Dans l'exemple ci-dessous, nous utilisons TreeMappour trier les clés dans un fichier Map.

 public class TreeMapExample { public static void main(String... barney) { Map simpsonsCharacters = new TreeMap(); simpsonsCharacters.put(new SimpsonCharacter("Moe"), "shotgun"); simpsonsCharacters.put(new SimpsonCharacter("Lenny"), "Carl"); simpsonsCharacters.put(new SimpsonCharacter("Homer"), "television"); simpsonsCharacters.put(new SimpsonCharacter("Barney"), "beer"); System.out.println(simpsonsCharacters); } } 

TreeMaputilise la compareTo()méthode implémentée par l' Comparableinterface. Chaque élément du résultat Mapest trié par sa clé. Dans ce cas, la sortie serait:

 Barney=beer, Homer=television, Lenny=Carl, Moe=shotgun 

Souvenez-vous cependant: si l'objet ne s'implémente pas Comparable, un ClassCastExceptionsera lancé.

Tri d'un ensemble avec TreeSet

L' Setinterface est responsable du stockage des valeurs uniques, mais lorsque nous utilisons l'implémentation TreeSet, les éléments insérés seront automatiquement triés au fur et à mesure que nous les ajoutons:

 public class TreeSetExample { public static void main(String... barney) { Set simpsonsCharacters = new TreeSet(); simpsonsCharacters.add(new SimpsonCharacter("Moe")); simpsonsCharacters.add(new SimpsonCharacter("Lenny")); simpsonsCharacters.add(new SimpsonCharacter("Homer")); simpsonsCharacters.add(new SimpsonCharacter("Barney")); System.out.println(simpsonsCharacters); } } 

La sortie de ce code est:

 Barney, Homer, Lenny, Moe 

Encore une fois, si nous utilisons un objet qui ne l'est pas Comparable, un ClassCastExceptionsera lancé.

Tri avec comparateur

Et si nous ne voulions pas utiliser la même compareTo()méthode de la classe POJO? Pouvons-nous remplacer la Comparableméthode pour utiliser une logique différente? Voici un exemple:

 public class BadExampleOfComparable { public static void main(String... args) { List characters = new ArrayList(); SimpsonCharacter homer = new SimpsonCharacter("Homer") { @Override public int compareTo(SimpsonCharacter simpson) { return this.name.length() - (simpson.name.length()); } }; SimpsonCharacter moe = new SimpsonCharacter("Moe") { @Override public int compareTo(SimpsonCharacter simpson) { return this.name.length() - (simpson.name.length()); } }; characters.add(homer); characters.add(moe); Collections.sort(characters); System.out.println(characters); } } 

As you can see, this code is complicated and includes a lot of repetition. We had to override the compareTo() method twice for the same logic. If there were more elements we would have to replicate the logic for each object.

Fortunately, we have the Comparator interface, which lets us detach the compareTo() logic from Java classes. Consider the same example above rewritten using Comparator:

 public class GoodExampleOfComparator { public static void main(String... args) { List characters = new ArrayList(); SimpsonCharacter homer = new SimpsonCharacter("Homer"); SimpsonCharacter moe = new SimpsonCharacter("Moe"); characters.add(homer); characters.add(moe); Collections.sort(characters, (Comparator. comparingInt(character1 -> character1.name.length()) .thenComparingInt(character2 -> character2.name.length()))); System.out.println(characters); } } 

These examples demonstrate the main difference between Comparable and Comparator.

Use Comparable when there is a single, default comparison for your object. Use Comparatorwhen you need to work around an existing compareTo(), or when you need to use specific logic in a more flexible way. Comparator detaches the sorting logic from your object and contains the compareTo() logic within your sort() method.

Using Comparator with an anonymous inner class

In this next example, we use an anonymous inner class to compare the value of objects. An anonymous inner class, in this case, is any class that implements Comparator. Using it means we are not bound to instantiating a named class implementing an interface; instead, we implement the compareTo() method inside the anonymous inner class.

 public class MarvelComparator { public static void main(String... comparator) { List marvelHeroes = new ArrayList(); marvelHeroes.add("SpiderMan "); marvelHeroes.add("Wolverine "); marvelHeroes.add("Xavier "); marvelHeroes.add("Cyclops "); Collections.sort(marvelHeroes, new Comparator() { @Override public int compare(String hero1, String hero2) { return hero1.compareTo(hero2); } }); Collections.sort(marvelHeroes, (m1, m2) -> m1.compareTo(m2)); Collections.sort(marvelHeroes, Comparator.naturalOrder()); marvelHeroes.forEach(System.out::print); } } 

More about inner classes

An anonymous inner class is simply any class whose name doesn’t matter, and which implements the interface we are declaring. So in the example, the new Comparator is actually the instantiation of a class that doesn’t have a name, which implements the method with the logic we want.

Using Comparator with lambda expressions

Anonymous inner classes are verbose, which can cause problems in our code. In the Comparator interface, we can use lambda expressions to simplify and make the code easier to read. For example, we could change this:

 Collections.sort(marvel, new Comparator() { @Override public int compare(String hero1, String hero2) { return hero1.compareTo(hero2); } }); 

to this:

 Collections.sort(marvel, (m1, m2) -> m1.compareTo(m2)); 

Less code and the same result!

The output of this code would be:

 Cyclops SpiderMan Wolverine Xavier 

We could make the code even simpler by changing this:

 Collections.sort(marvel, (m1, m2) -> m1.compareTo(m2)); 

to this:

 Collections.sort(marvel, Comparator.naturalOrder()); 

Lambda expressions in Java

Learn more about lambda expressions and other functional programming techniques in Java.

Are the core Java classes Comparable?

Many core Java classes and objects implement the Comparable interface, which means we don’t have to implement the compareTo() logic for those classes. Here are a few familiar examples:

String

 public final class String implements java.io.Serializable, Comparable, CharSequence { ... 

Integer

 public final class Integer extends Number implements Comparable { … 

Double

 public final class Double extends Number implements Comparable {... 

There are many others. I encourage you to explore the Java core classes to learn their important patterns and concepts.

Relevez le défi de l'interface comparable!

Testez ce que vous avez appris en déterminant la sortie du code suivant. N'oubliez pas que vous apprendrez mieux si vous résolvez ce défi par vous-même simplement en l'étudiant. Une fois que vous avez atteint une réponse, vous pouvez vérifier la réponse ci-dessous. Vous pouvez également exécuter vos propres tests pour absorber pleinement les concepts.

 public class SortComparableChallenge { public static void main(String... doYourBest) { Set set = new TreeSet(); set.add(new Simpson("Homer")); set.add(new Simpson("Marge")); set.add(new Simpson("Lisa")); set.add(new Simpson("Bart")); set.add(new Simpson("Maggie")); List list = new ArrayList(); list.addAll(set); Collections.reverse(list); list.forEach(System.out::println); } static class Simpson implements Comparable { String name; public Simpson(String name) { this.name = name; } public int compareTo(Simpson simpson) { return simpson.name.compareTo(this.name); } public String toString() { return this.name; } } } 

Quelle est la sortie de ce code?

 A) Bart Homer Lisa Maggie Marge B) Maggie Bart Lisa Marge Homer C) Marge Maggie Lisa Homer Bart D) Indeterminate