Tri d'une List

**Raikyn** · 30/03/2015, 17h21

Bonjour,

J'ai le code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
public static <K, V extends Comparable<? super V>> Map<K, V> 
				sortByValue( Map<K, V> map )
    {
        List<Map.Entry<K, V>> list =
            new LinkedList<Map.Entry<K, V>>( map.entrySet() );
        Collections.sort( list, new Comparator<Map.Entry<K, V>>()
        {
            public int compare( Map.Entry<K, V> o1, Map.Entry<K, V> o2 )
            {
                return (o1.getValue()).compareTo( o2.getValue() );
            }
        } );
	List<Map.Entry<K, V>> list2 = Collection.reverse(list);
 
        Map<K, V> result = new LinkedHashMap<K, V>();
        for (Map.Entry<K, V> entry : list)
        {
            result.put( entry.getKey(), entry.getValue() );
        }
        return result;
    }

Cela trie une HashMap (suivant la valeur) dans l'ordre croissant. Ce code n'est pas de moi, je l'ai trouvé sur le net.
Je ne suis pas familier avec les Collection mais il semblerait que pour faire le trie d'une hashMap, ce code met le contenu de la hashMap dans une List pour ensuite trier la List (et renvoyer une hashMap à partir de cette List).
J'aimerai trier dans un ordre décroissant, comment faire ?
J'ai essayer :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Collection.reverse(list)

mais cela ne marche pas.
Auriez vous une solution ?

Merci d'avance pour votre aide.

**joel.drigo** · 30/03/2015, 17h32

Salut,

Collections.reverse(liste) c'est pour inverser l'ordre actuel des éléments dans la liste : ça ne trie rien du tout. Le code que tu as pris trie les entrées de la map (association clef/valeurs) selon les valeurs, puis inverse la liste triées de ces entrées puis les range dans une LinkedHashMap pour conserver cet ordre (parce qu'une simple HashMap ne conserve pas l'ordre).

La ligne qui fait le tri est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Collections.sort( list, new Comparator<Map.Entry<K, V>>()
        {
            public int compare( Map.Entry<K, V> o1, Map.Entry<K, V> o2 )
            {
                return (o1.getValue()).compareTo( o2.getValue() );
            }
        } );

On peut se demander pourquoi on tri dans un ordre puis on inverse l'ordre, plutôt que de trier dans le bon ordre dès le départ ?

Toujours est-il qu'on utilise Collections.sort(list) ou Collections.sort(liste, comparator) : le premier pour trier des éléments qui ont un ordre naturel (soit qui implémente l'interface Comparable), comme des String, des Integer, des Dates.
Pour les autres, il faut utiliser la seconde version et implémenter un Comparator qui dira justement quel est l'ordre entre 2 éléments, quels qu'ils soient.

Pour trier dans l'ordre inverse de l'ordre naturel, il faut donc utiliser un comparator : mais il existe déjà, tu n'as pas besoin de l'implémenter. Tu peux l'obtenir par Collections.reverseOrder().

Par exemple pour trier une liste d'entiers (ou de tout autre Comparable) dans l'ordre inverse de l'ordre naturel, donc décroissant pour les entiers, entre autres :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  Collections.sort( liste, Collections.reverseOrder() );

Ou en Java 8, plus logiquement peut-être :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  Collections.sort( liste, Comparator.reverseOrder() );

**Raikyn** · 30/03/2015, 21h57

Donc il faudrait que je remplace le tri :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Collections.sort( list, new Comparator<Map.Entry<K, V>>()
        {
            public int compare( Map.Entry<K, V> o1, Map.Entry<K, V> o2 )
            {
                return (o1.getValue()).compareTo( o2.getValue() );
            }
        } );

Par:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Collections.sort( liste, Collections.reverseOrder() );

Le truc c'est que reverseOrder() n'est pas une méthode de Collection ou Comparato, ça ne compile pas.

**joel.drigo** · 30/03/2015, 22h03

Pas de Collection, de Collections ou de Comparator, à partir de Java 8.

**Raikyn** · 30/03/2015, 22h12

Ah d'accord!
Bon alors ça compile mais j'ai une erreur à l'execution :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
Exception in thread "main" java.lang.ClassCastException: java.util.HashMap$Entry cannot be cast to java.lang.Comparable
	at java.util.Collections$ReverseComparator.compare(Collections.java:3569)
	at java.util.TimSort.countRunAndMakeAscending(TimSort.java:324)
	at java.util.TimSort.sort(TimSort.java:203)
	at java.util.TimSort.sort(TimSort.java:173)
	at java.util.Arrays.sort(Arrays.java:659)
	at java.util.Collections.sort(Collections.java:217)
	at Zipf.sortByValue(Zipf.java:97)
	at Zipf.<init>(Zipf.java:17)
	at Interface.<init>(Interface.java:19)
	at Interface.main(Interface.java:95)

**joel.drigo** · 30/03/2015, 22h28

Mais c'est une List (le titre de ta discussion) ou une Map que tu cherches à trier ? Comment ça se fait que tu tries des Map.Entry ?

**Raikyn** · 30/03/2015, 23h09

En fait c'est une hashMap que je veux trier mais apparement la seule façon de tier une hashMap en fonction des valeurs c'est en passant par une List (enfin y'a pas de méthode prédéfinie pour ça), c'est pour ça que j'ai mis "List" dans le titre du topic.
Là il faudrait donc redéfinir un Comparator alors ?

**joel.drigo** · 30/03/2015, 23h11

Et tu veux trier la map sur les valeurs ou sur les clefs ? Tu es obligé de rester sous Java 7 ou tu peux passer sous Java 8 ?

**Raikyn** · 31/03/2015, 11h28

Je voudrais trier sur les valeurs (qui sont des int), et j'ai essayé à l'instant d'installer java 8 mais ça ne marche appremment pas. Il faudrait peut-être que je mette à jour ma version d'Ubuntu...

**joel.drigo** · 31/03/2015, 11h47

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class MapUtils {
 
	// Java 7
	public static <K,V> Map<K, V> sortByValues(Map<K,V> map, final Comparator<V> comparator) {
 
		final Set<Map.Entry<K,V>> sortedEntries = new TreeSet<Map.Entry<K,V>>(new Comparator<Map.Entry<K,V>>() {
			@Override
			public int compare(Map.Entry<K, V> e1, Map.Entry<K, V> e2) {
				return comparator.compare(e1.getValue(), e2.getValue());
			}
		});
		sortedEntries.addAll(map.entrySet());
 
		final Map<K, V> sortedMap = new LinkedHashMap<K, V>();
		for(Map.Entry<K, V> entry : sortedEntries) {
			sortedMap.put(entry.getKey(), entry.getValue());
		}
 
		return sortedMap;
 
	}
 
	/*
	// Java 8
	public static <K,V> Map<K, V> sortByValues(Map<K,V> map, Comparator<V> comparator) {
 
		return map.entrySet()
		          .stream()
		          .sorted((e1,e2)-> comparator.compare(e1.getValue(), e2.getValue()))
	                  .collect(Collectors.toMap(e->e.getKey(),e->e.getValue(),(v1,v2)->v1,LinkedHashMap::new));
 
	}
	*/
 
 
	public static void main(String[] args) {
 
		Map<String, Integer> map = new HashMap<String, Integer>();
 
		map.put("A",1);
		map.put("B",4);
		map.put("C",2);
		map.put("D",3);
 
 
		map = MapUtils.sortByValues(map, Collections.reverseOrder()); // Java 7
		//map = MapUtils.sortByValues(map, Comparator.reverseOrder()); // Java 8
 
		System.out.println(map);
 
	}
 
}

**Pill_S** · 31/03/2015, 13h20

Laisse tomber Java 8 pour l'instant, ça t'apportera rien de plus que des maux de tête... et mieux vaut apprendre à bosser à l'ancienne au début

**joel.drigo** · 31/03/2015, 14h11

Envoyé par Pill_S

Laisse tomber Java 8 pour l'instant, ça t'apportera rien de plus que des maux de tête... et mieux vaut apprendre à bosser à l'ancienne au début

On peut passer à Java 8 sans forcément utiliser (toutes) les nouvelles fonctionnalités (si tant est qu'elles pourraient apporter des maux de tête à certains). On peut monter doucement en compétence sur ces nouvelles fonctionnalités, sans se fermer aucune porte. Rester en Java 7 fera petit à petit que beaucoup d'exemples trouvés sur ici ou là, ou même des bibliothèques, ne fonctionneront plus, et ça, ça peut devenir rapidement prise de tête.

**Raikyn** · 31/03/2015, 14h34

Merci pour le code, cela tri bien dans un ordre décroissant cependant la liste "sortedEntries" n'a pas les doublons (et j'en ai besoin).

**joel.drigo** · 31/03/2015, 14h47

Envoyé par Raikyn

Merci pour le code, cela tri bien dans un ordre décroissant cependant la liste "sortedEntries" n'a pas les doublons (et j'en ai besoin).

Ah, oui, je n'avais pas pensé à cet aspect.

Sans dédoublemenage :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static <K,V> Map<K, V> sortByValues(Map<K,V> map, final Comparator<V> comparator) {
 
			final List<Map.Entry<K,V>> sortedEntries = new ArrayList<>(map.entrySet());
			Collections.sort(sortedEntries, new Comparator<Map.Entry<K,V>>() {
				@Override
				public int compare(Map.Entry<K, V> e1, Map.Entry<K, V> e2) {
					return comparator.compare(e1.getValue(), e2.getValue());
				}
			});
 
			final Map<K, V> sortedMap = new LinkedHashMap<K, V>();
			for(Map.Entry<K, V> entry : sortedEntries) {
				sortedMap.put(entry.getKey(), entry.getValue());
			}
 
			return sortedMap;
 
		}

Par contre, dans ce cas, il n'y a pas de garantie sur la stabilité de l'ordre des clefs associées à une même valeur.

On pourrait utiliser ça, le second comparateur étant utilisé pour les valeurs égales :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static <K,V> Map<K, V> sortByValues(Map<K,V> map, final Comparator<V> comparator, final Comparator<K> secondaryComparator) {
 
			final List<Map.Entry<K,V>> sortedEntries = new ArrayList<>(map.entrySet());
			Collections.sort(sortedEntries, new Comparator<Map.Entry<K,V>>() {
				@Override
				public int compare(Map.Entry<K, V> e1, Map.Entry<K, V> e2) {
					int compare = comparator.compare(e1.getValue(), e2.getValue());
					if ( compare==0 ) {
						return secondaryComparator.compare(e1.getKey(), e2.getKey());
					}
					return compare;
				}
			});
 
			final Map<K, V> sortedMap = new LinkedHashMap<K, V>();
			for(Map.Entry<K, V> entry : sortedEntries) {
				sortedMap.put(entry.getKey(), entry.getValue());
			}
 
			return sortedMap;
 
		}

Voire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static <K,V> Map<K, V> sortByValues(Map<K,V> map, final Comparator<V> comparator, final Comparator<Map.Entry<K,V>> secondaryComparator) {
 
			final List<Map.Entry<K,V>> sortedEntries = new ArrayList<>(map.entrySet());
			Collections.sort(sortedEntries, new Comparator<Map.Entry<K,V>>() {
				@Override
				public int compare(Map.Entry<K, V> e1, Map.Entry<K, V> e2) {
					int compare = comparator.compare(e1.getValue(), e2.getValue());
					if ( compare==0 ) {
						return secondaryComparator.compare(e1, e2);
					}
					return compare;
				}
			});
 
			final Map<K, V> sortedMap = new LinkedHashMap<K, V>();
			for(Map.Entry<K, V> entry : sortedEntries) {
				sortedMap.put(entry.getKey(), entry.getValue());
			}
 
			return sortedMap;
 
		}

**Raikyn** · 31/03/2015, 14h50

En fait j'ai réussi à trier dans le bon ordre. J'ai simplement mis un moins ici :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

return -(o1.getValue()).compareTo(o2.getValue());

Merci pour le coup de main

Edit: je vais tester ton code, ça m'a l'air plus propre que ma magouille.

**joel.drigo** · 31/03/2015, 15h01

Envoyé par Raikyn

En fait j'ai réussi à trier dans le bon ordre. J'ai simplement mis un moins ici :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

return -(o1.getValue()).compareTo(o2.getValue());

Merci pour le coup de main

Edit: je vais tester ton code, ça m'a l'air plus propre que ma magouille.

Non, ce n'est pas de la magouille, c'est ce qu'on fait habituellement (c'est d'ailleurs pour ça que je disais dans mon post 2 :

Envoyé par joel.drigo

On peut se demander pourquoi on tri dans un ordre puis on inverse l'ordre, plutôt que de trier dans le bon ordre dès le départ ?

C'est exactement à cette solution que je pensais au lieu de faire un Collections.reverse() après. Par contre, je ne vois pas pourquoi tu le fais dans le code initial alors qu'il y a un reverseOrder() après ? Autant tout simplement enlever le reverseOrder() si l'ordre n'est pas celui que tu attends.

La solution que j'ai donnée fonctionne simplement pour toutes les classes Comparable ou pas, mais il faut fournir un comparateur. En Java 8, c'est plus simple pour comparer selon l'ordre naturel, puisqu'on a Comparators.naturalOrder() alors qu'en Java 7, on doit se faire une classe (ce qui n'est pas du tout compliqué).

Tri d'une List

Java

Discussions similaires

Partager

Partager