Le tri en java

Voici une brève présentation de la méthode statique Collections.sort (ou Arrays.sort) qui sert à trier des listes (tableaux).
Cette méthode délègue au client (l'appelant) le soin de préciser l'algorithme de tri à utiliser pour ordonner la liste.
C'est une bonne illustration du design pattern "strategy".
Nous nous intéressons ici, aux aspects techniques uniquement.
Partons de situations réelles, qui seront illustrées par des tests unitaires (JUnit 4).

En réalité, lorsqu'on souhaite trier une liste, on se trouve face à l'une des trois situations suivantes :

  1. La liste contient des éléments de types primitifs ou bien contient des objets implémentant l'interface Comparable ;
  2. La liste contient des objets qui n'implémentent pas l'interface Comparable ;
  3. Les objets de la liste implémentent Comparable mais l'algorithme de tri de cette interface n'est pas approprié.

Première signature de la méthode Collections.sort(java.util.List liste)

Collections.sort(List liste) prend un seul argument qui est la liste à trier.
Elle répond à la première situation.
Le résultat de l'appel de cette méthode, avec pour argument une liste contenant des éléments de types primitifs ou des objets implémentant Comparable, est une liste bien ordonnée selon l'algorithme naturel ou celui défini par l'interface Comparable.

Petit test:

[java]

String [] fruits ={ "Pomme","Abricot","Kiwi"};
List listeFruits=new ArrayList<String>(Arrays.asList(fruits)};

Collections.sort(listeFruits); // resultat "Abricot","Kiwi","Pomme"

Seconde signature de la méthode Collections.sort(List liste, java.util.Comparator c)

Cette seconde signature répond à la seconde et troisième situations.

Démo1:

[java]
public class Personne {
	private String nom;
	private String prenom;
	private Date dateNce;
	private transient SimpleDateFormat sdf
      =new SimpleDateFormat("dd/MM/yyyy");

	public Personne(String nom, String 
prenom, String sDate) {
		this.nom = nom;
		this.prenom = prenom;
		try {
			this.dateNce= sdf.parse(sDate);
		} catch (ParseException e) {
			this.setDateNce(null);
		}
	}
	public String toString() {
		return "nom=" + nom 
         + " prénom=" + prenom 
         + " né(e) le "+ sdf.format(dateNce) 
         + " ";
	}

       // les getters setters sont omis..

Créons un test unitaire Junit4.x avec la méthode de test suivante :


@Test public void testTri(){
		// echantillon 
		Personne tato= new Personne(
"Tato","Tato","12/02/2000");  
		Personne tato2= new Personne(
"Tato","Tato","12/01/2000");
		Personne tete= new Personne(
"Tete","Tete","11/01/2000");
		Personne tete2= new Personne(
"Tete","Tete","10/01/2000");
		Personne[] personnes=
{tato,tato2,tete,tete2};
		
		List<Personne> listePers=new ArrayList<Personne>(
                  Arrays.asList(personnes) );
		
   System.out.println("\nAvant:\n"+listePers);
				
   Collections.sort(listePers, new Comparator<Personne>() {

	@Override
	public int compare(Personne p1,  Personne p2) {
	if ( p1==null){
	  if(p2!=null) return -1;
        }
        if (p2==null) return 1;
	int result= p1.getNom().compareTo(p2.getNom());
        if(result==0) result=p1.getPrenom().compareTo(p2.getPrenom());
        if(result==0) result=p1.getDateNce().compareTo(p2.getDateNce());
	return result;
 }
});	
	
  System.out.println("\nApres tri:\n"+listePers);

Il est vrai que le test unitaire n'utilise pas d'assert.
Je vous laisserai le soin d'ajouter une assertion avec par exemple Assert.assertEqualst(List,List).

On obtient l'affichage suivant comme résultat de ce test :

Avant:
[nom=Tato prénom=Tato né(e) le 12/02/2000 , 
 nom=Tato prénom=Tato né(e) le 12/01/2000 , 
 nom=Tete prénom=Tete né(e) le 11/01/2000 , 
 nom=Tete prénom=Tete né(e) le 10/01/2000 ]

Apres tri:
[nom=Tato prénom=Tato né(e) le 12/01/2000 , 
 nom=Tato prénom=Tato né(e) le 12/02/2000 , 
 nom=Tete prénom=Tete né(e) le 10/01/2000 , 
 nom=Tete prénom=Tete né(e) le 11/01/2000 ]

Explications:
La seule chose qui mérite d'être expliquée est le second argument de la méthode sort qui est une classe anonyme d'implémentation de l'interface Comparator.
Enfin, le tri se fait d'abord par nom (ordre alphabétique croissant) puis par prénom (ordre alphabétique croissant) et enfin par date de naissance (ordre croissant).
C'est justement ce que fait le code :

        int result= p1.getNom().compareTo(p2.getNom());
        if(result==0) 
            result=p1.getPrenom().compareTo(p2.getPrenom());
        if(result==0) 
            result=p1.getDateNce().compareTo(p2.getDateNce());

En résumé, la méthode Collections.sort répond aux trois situations possibles évoquées.
Son design qui respecte celui "Strategy" a permis d'adapter le bon algorithme pour effectuer le tri qui convient.
Tout ce qui a été fait pour les listes s'applique de la même manière aux tableaux avec Arrays.sort.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Captcha *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.