Etude de tris classiques

Nous présentons et comparons les divers algorithmes de tri présents dans l'enseignement d'informatique. Pour aider à la compréhension nous utilisons un petit programme d'animation de ces tris, qui nous permettra aussi d'avoir une démarche expérimentale (voir paragraphe III. Animation). Nous donnons également deux exemples de programmation, en langage C et en java, afin de montrer comment utiliser les possibilités de tri offertes dans ces langages.

Rappelons qu'un tri est indispensable afin de disposer d'une recherche efficace dès que les ensembles ont plus d'une centaine d'éléments; par exemple l'ensemble des dossiers des étudiants de la faculté d'Orsay a plus de 7000 éléments. Cette recherche, parmi les éléments d'un tableau est la recherche dichotomique qui ne s'applique que sur un tableau ordonné.

Les six méthodes de tri choisies, Sélection, Insertion, Bulle, Shell, Arbre et Rapide sont les plus classiques; certaines n'ont qu'un intérêt pédagogique, alors que d'autres ont, en plus, un intérêt pratique du fait de leur efficacité, en terme de temps d'exécution.
Ajoutons qu'il est question de trier un tableau sans utiliser beaucoup de mémoire supplémentaire. Donc lors de l'exécution de l'algorithme les éléments du tableau changent de place, en restant dans le tableau, et c'est toujours le même tableau, qui contient, à la fin les éléments en ordre croissant.
Nous supposons que les éléments à trier sont des nombres; ce n'est pas le cas le plus général des éléments à trier, mais cela permet une écriture plus simple des algorithmes (voir paragraphe Algorithmes).

Après une présentation qui se veut intuitive, au paragraphe I (Présentation), la comparaison des méthodes de tri est faite d'une part en évaluant le nombre d'opérations respectivement effectuées par chaque méthode; cette évaluation est soit expérimentale (voir paragraphe II.2 Nombre d'opérations) soit de nature plus mathématique au paragraphe IV. (Algorithmes) après l'écriture de chaque algorithme.
Le deuxième critère de comparaison présenté est le temps d'exécution nécessaire à un tri, au paragraphe II. (voir Comparaison en temps).
Il n'y a pas de comparaisons basées sur l'encombrement mémoire, car pour les six méthodes, la place occupée en mémoire n'excède pratiquement pas celle des données de départ; une petite restriction, à ce sujet, pour le tri rapide qui, étant récursif occupe plus de place à l'exécution.

I. Présentation des tris

Les éléments à trier, en nombre n, sont placés dans un tableau t; le premier élément est à l'indice 0 et le dernier est à l'indice n-1.

Notation si u et v sont des entiers positifs, au plus égaux à n-1, avec u <= v, on notera t[u .. v] le sous-tableau contenant les éléments d'indices u, u+1 ... v.

1. Tri sélection

On commence par déterminer le plus grand élément du tableau, que l'on place à l'indice n-1; puis on recommence la même démarche sur le sous- tableau t[0..n-2] ayant un élément de moins, puis sur le sous- tableau t[0..n-3] et ainsi de suite.
Ainsi à chaque étape un élément est mis à sa place définitive dans la suite triée. Le nom du tri provient de la démarche consistant à sélectionner la plus grande valeur, dans une suite.

2. Tri insertion

On construit d'abord le sous-tableau t[0..1] trié, puis le sous-tableau t[0..2] trié, puis t[0..3] trié et ainsi de suite. Pour passer d'un sous-tableau au suivant, par exemple de t[0..2] à t[0..3], on va insérer l'élément t[3] dans le sous-tableau de gauche; on exploite, pour cela, la propriété du sous-tableau, d'être trié.
La dernière étape consiste à insérer l'élément t[n-1] dans le sous-tableau t[0..n-2].

3. Tri bulle

(terme anglophone: bubble sort)
Dans un premier parcours du tableau complet, t[0..n-1], on compare des éléments consécutifs et on échange deux éléments, d'indice i et i+1, si t[i] < t[i+1]. A à la fin de ce premier parcours t[n-1] contient le plus grand élément du tableau.
On fait de même dans un deuxième parcours, en se limitant au sous-tableau t[0..n-2], puis dans un nouveau parcours, avec t[0..n-3] ...
Le dernier parcours est celui du tableau t[0..1].

4. Tri shell

Cette méthode est une amélioration astucieuse et efficace du tri insertion. Un inconvénient du tri insertion est que les échanges ne portent que sur des éléments consécutifs et souventi, lors du tri, un même élément changera plusieurs fois d'une seule position.

Monsieur Shell a donc pensé à travailler sur des sous tableaux dont les indices ne sont pas consécutifs afin que des éléments changent de plusieurs positions en une fois. Par exemple pour trier le tableau t[0..24]; il préconise de trier, par insertion, le sous-tableau t[0,4,8..24], puis les sous-tableaux t[1,5,9..21], t[2,6,10..22] et t[3,7,11..23]. On est donc sur des sous-tableaux dont les éléments sont distants d'un pas de 4 sur cet exemple.
Il faut, pour terminer, trier le tableau t[0,1..24], pour lequel le pas est de 1 .

Cela paraît inutilement compliqué et pourtant ... c'est efficace. On commence par un pas de l'ordre de n / 10, puis on diminue le pas, jusqu'au dernier sous-tableau qui est t[0,1..n-1], correspondant à un pas de 1.

5. Tri arbre

Ce tri, aussi appelé tri par tas (terme anglophone heapsort), est basé sur une organisation particulière des éléments d'un tableau appelé tas.
Il utilise les propriétés suivantes d'un tableau t[0 .. n-1] organisé en un tas :
  1. t[0] est le plus grand élément de t[0 .. n-1] ;
  2. t[0 .. n-2] est aussi un tas (conservation de la propriété en enlevant le dernier élément);
  3. si on modifie la valeur t[0], on n'a plus un tas mais on peut le reconstituer par un très petit nombre d'échanges.
La méthode comporte deux phases. Dans la première phase on va organiser t[0 .. n-1] en un tas. Dans la deuxième phase on a une succession d'étapes: échanger t[0] et t[n-1] qui contient alors le plus grand élément du tableau, puis réorganiser t[0 .. n-2] en un tas. Recommencer les mêmes opérations successivement sur les sous-tableaux t[0 .. n-2], ... t[0 .. 1].

6. Tri rapide

Le tri rapide (terme anglophone quicksort) se comprend bien avec une présentation récursive.
On doit trier le tableau t[0 .. n-1]; on s'intéresse à l'élément a = t[0].

II. Comparaisons des méthodes

Nous comparons ces méthodes de tris de deux façons. Nous ne parlons pas ici des calculs théoriques de complexité, en fonction de la taille du tableau, qui sont esquissés au paragraphe IV.
En adoptant une approche plus expérimentale, les comparaisons sont basées sur des mesures de temps d'exécution et de nombres d'opérations sur les éléments des tableaux.

1. Temps d'exécution

Après avoir programmé les 6 méthodes en Java et en générant de façon aléatoire des tableaux de nombres, nous avons mesuré les temps d'exécution pour chaque méthode, triant le même tableau. Nous avons aussi modifié la taille des tableaux, afin de voir comment varie le temps d'exécution en fonction de la taille.

Ces temps d'exécution ne sont pas très précis; ils ont une précision de l'ordre de 40% pour une mesure d'une seconde; cette précision baisse à 5% quand la mesure depasse 200 secondes.
Les temps servent toutefois d'éléments de comparaison, soit entre méthodes de tris, soit entre tailles différentes.

Temps d'exécution en millisecondes,
suivant la taille et la méthode
tableau aléatoire
    Taille     SélectionInsertionBulle ShellArbreRapide
640 3.81.68.2 0.60.40.7
6400 329.0138.0873.0 8.86.19.6
64000 35756.017698.096878.0 131.082.066.0
640000 - - -- - -- - - 2241.01235.0824.0

Nous allons voir si la méthode de tri s'adapte à l'organisation initiale des valeurs du tableau.
Ci dessous on a trié des tableaux pour lesquels 15% des valeurs environ sont mal placées: si on les supprime, le reste des valeurs est en ordre croissant dans le tableau.

Temps d'exécution en millisecondes,
suivant la taille et la méthode
tableau presque trié
    Taille     SélectionInsertionBulle ShellArbreRapide
640 3.30.65.5 0.40.40.8
6400 351.022.0588.0 7.15.511.0
64000 34888.02802.065242.0 115.072.088.0
640000 - - -- - -- - - 1879.0834.01143.0

2. Nombre d'opérations

Ayant programmé les algorithmes de tris, nous pouvons compter, lors d'une exécution, le nombre de comparaisons effectuées; nous ne comptons que les comparaisons entre éléments à trier; par exemple si nous trions des chaînes de caractères, nous décomptons le nombre de comparaisons entre chaînes, et ignorons les comparaisons entre indices, qui peuvent intervenir dans la programmation.
Nous dénombrons aussi les nombres d'accès aux éléments du tableau, en distinguant un examen de la valeur d'un élément, appelé accès en lecture , de la modification de la valeur, appelé accès en écriture.
Par exemple, dans les instructions:
a = t[i];     il y a un accès, en lecture au tableau t
if ( a < t[i] ) ...     il y a un accès, en lecture au tableau t
et une comparaison entre éléments à trier
t[i] = a;     il y a un accès, en écriture au tableau t

Plus l'algorithme est efficace et plus petit est le nombre d'opérations mesuré. Comparer ces nombres permet de mieux comprendre les avantages d'une méthode par rapport à une autre. Le tableau ci-dessous présente des mesures effectuées lors de tris de tableau générés de façon aléatoire; nous présentons deux tailles différentes, 640 ou 6400 éléments, ce qui suffit à éclairer les particularités de chaque tri.

Nombre d'opérations
suivant la taille et la méthode
Mesures Taille SélectionInsertionBulle ShellArbreRapide
nb.comparaisons 640 2044805081203850 4970100337169
6400 204768007208120472047 9292414242691981
nb.lectures640 209327105480612354 12961221919691
6400 205322511031490161223214 229012306223127727
nb.ecritures640 1278100399204654 799171802636
6400 1279981024282020279120 1360889298736836

III. Animation des tris

Une applet java permet d'illustrer les modifications des éléments du tableau pour réaliser les différences entre les méthodes.

1. Présentation

La première fenêtre montre un diagramme à barres qui, en fait, représente les éléments d'un tableau tiré au sort; les indices sont surmontés d'une barre de longueur proportionnelle à la valeur de l'élément.
En dessous de ce diagramme figure l'affichage de quelques valeurs numériques: taille du tableau, méthode utilisée pour le trier, temps nécessaire en millisecondes (intitulé millis.s), nombre de comparaisons pour trier(intitulé nb.cmp), nombre de lectures dans le tableau (intitulé nb.lec) et nombre d'écritures dans le tableau (intitulé nb.écr).

Tout en bas figure une barre de commandes, permettant, pour un tableau, de choisir : sa taille, son contenu (aléatoire, déjà trié en ordre croissant, trié en ordre décroissant, ou presque trié) et la méthode de tri.
On trouve deux boutons nommés 'Une étape' et 'Tri complet' qui permettent respectivement de voir l'évolution des éléments d'un tableau pendant une étape de tri ou durant le tri complet.
On trouve enfin une liste de deux choix 'Tri/Résultats' permettant de modifier l'affichage dans le panneau central.

2. Bouton 'Tri complet'

Dans la représentation des éléments de tableaux lors d'un tri, on dessine en blanc un élément qui se trouve placé, du fait du tri, à sa place définitive, même si l'opération de tri n'est pas encore terminée.

Essais
  1. Choisir une taille de '64', un type 'aléa.' et la méthode 'Sélection'. Appuyer alors sur 'Tri complet', et voir le tableau se déformer, avec la partie gauche, en blanc, contenant les éléments les plus grands, qui s'aggrandit.
  2. Choisir ensuite la méthode 'Insertion'; le même tableau non trié est affiché; appuyer alors sur 'Tri complet', pour voir la partie droite, formée d'éléments en ordre croissant, qui s'agrandit pour devenir le tableau complet; à la fin tous les éléments étant rangés, ils apparaissent en blanc.
  3. Choisir la méthode 'Bulle'; le même tableau non trié est à nouveau affiché dans son état initial, non trié.
    Appuyer alors sur 'Tri complet', pour voir la partie droite, formée des éléments les plus grands, marqués en blanc car ils sont à leur place définitive (ils ne bougent plus), qui s'aggrandit sur la gauche pour devenir le tableau complet.
    Ce comportement ressemble à celui du 'Insertion'
  4. Choisir la méthode 'Shell' et lancer le 'Tri complet'. On voit des éléments qui changent de place, sans réaliser de quelle façon, puis le tableau trié est affiché. Une autre animation nous permettra de mieux d'appréhender cette méthode.
  5. Choisir la méthode 'Arbre' et lancer le 'Tri complet'. Dans une première phase de changements paraissant confuse, les éléments les plus grands vont vers la gauche. Puis dans une deuxième phase, on voit la partie droite, formée des éléments les plus grands, tracés en blanc, qui s'aggrandit sur la gauche pour devenir le tableau complet, comme avec le 'Arbre', mais plus rapidement.
  6. Choisir enfin la méthode 'Rapide' et lancer le 'Tri complet'. Des éléments tracés en blanc apparaissent, au milieu, à gauche ou à droite, ne changent plus de place, et leur nombre augmente jusqu'au tri complet.

3. Bouton 'Une étape'

On va voir l'évolution des éléments d'un tableau lors d'une étape de tri; la notion d'étape a été présentée, pour chaque tri, dans le paragraphe de présentation des tris.

Quelques essais
Pour les tris Sélection, Insertion ou Bulle, on peut travailler avec une taille de 8, alors que pour les tris Shell, Arbre ou Rapide, il vaut mieux prendre une taille de 16.

4. Choix 'Tri / Résultats'

Après avoir fait des tris complets, on peut voir afficher des résultats numériques sur les nombres d'opérations effectuées et éventuellement les temps de tri. Cela permet de faire des comparaisons entre divers de tris travaillant sur le même tableau, ou un même tri utilisé pour des tableaux de type différents.

Exemples

IV. Algorithmes

Nous présentons une programmation en java des différentes méthodes de tri; la programmation en C ou C++ est extrêmement proche. Nous avons choisi de trier des tableaux de 'double' dans un souci de simplicité de présentation, alors que dans la pratique on distingue les enregistrements à trier des clés permettant d'ordonner les enregistrements. Voir le paragraphe Programmation pour un exemple avec des enregistrements.

Après chaque algorithme nous rappelons les résultats de complexité, en nombre d'opérations.

Le tableau à trier est le champ déclaré double t[], de la classe contenant aussi les méthodes triSelection, triInsertion ...

1. Tri sélection

void triSelection() { double max; int aRanger, j, jmax, n=t.length; for( aRanger=n-1; aRanger>0; aRanger--) { // Etape: chercher le max de t[0..aRanger] jmax=aRanger; max=t[jmax]; for(j=0; j<aRanger; j++) { if(t[j] > max) { jmax=j; max=t[jmax]; } } // ranger le max: échanger max en t[jmax] et t[aRanger] t[jmax]=t[aRanger]; t[aRanger]=max; } }

2. Tri insertion

void triInsertion() { double val; int tst; // taille du sous tableau trié int j, k, im, n=t.length ; for( tst=1; tst<n; tst++) { //ici t[0..tst-1,] est trié val = t[tst]; // Etape: où ranger val dans le sous-tableau trié t[0..tst-1] j=-1; k=tst; // recherche dichotomique while( j < k-1) { im = (j+k)/2; // indice du milieu de t[j+1 .. k-1] if( val < t[im] ) k=im; else j=im; //ici t[j] <= val < t[k]; } // Décalages et insertion for( k=tst-1; k>j; k-- ) t[k+1]=t[k]; t[j+1] = val; // ici t[0..tst-1,tStTtie] est trié } }

3. Tri bulle

void triBulle() { double vaux; int aRanger, nEchange=1, j, n=t.length; for( aRanger=n-1; nEchange>0 && aRanger>0; aRanger--) { // Etape: en parcourant t[0..aRanger], on échange 2 éléments // consécutifs s'ils ne sont pas dans l'ordre croissant nEchange=0; for(j=0; j<aRanger; j++) { if(t[j] > t[j+1]) { nEchange++; vaux=t[j]; t[j]=t[j+1]; t[j+1]=vaux; } } //ici t[aRanger] est le max de t[0..aRanger] } }

4. Tri Shell

La programmation, basée sur celle du tri Insertion, reprend le même type d'instructions pour trier des sous-tableaux dont les éléments sont séparés de pas indices. La valeur de pas doit diminuer, et pour le dernier tableau à trier, elle doit être de 1. void triShell() { double val; int i0, i,j,k, pas, n=t.length; // pas initialisé à environ n/9 pas=1; while(9*pas<n) pas=3*pas+1; for( ; pas > 0; pas /= 3) { // Etape: Tri des sous-tableaux (éléments distants de pas) for( i0=0; i0<pas; i0++) { // tri de t[i0,i0+pas,i0+2*pas ..] for( i=i0+pas; i<n; i+=pas) { //ici t[i0,i0+pas..i-pas] est trié val = t[i]; // où placer val dans le sous-tableau t[i0,i0+pas..i-pas] ? j=i-pas; while(j >= 0 && t[j] > val) j-=pas; // décalages et insertion de val en j+pas for( k=i-pas; k>j; k-=pas) t[k+pas]=t[k]; t[j+pas] = val; //ici t[i0 .. i-pas, i] est trié } } } }

5. Tri arbre

La programmation est basée sur l'interprétation des éléments d'un tableau comme un arbre binaire partiellement équilibré; rappelons la relation entre l'indice d'un sommet et ceux de ses fils (cas où 0 est le premier indice du tableau):
les fils du sommet d'indice i ont respectivement:
      l'indice 2*i+1 (fils gauche)
      l'indice 2*i+2 (fils droit)
Dans ce tri, la structure de tas est utilisée. Définition: les éléments sont organisés en un tas quand, pour tout sommet et ses fils, la valeur portée par le sommet est supérieure aux valeurs portées par ses fils.

L'algorithme de tri est plus clair quand il est présenté en utilisant le sous programme reorganiser qui organise des éléments de sous-tableau en un tas.

void triArbre() { int i, imax, n=t.length; double aux; // Phase 1: créer un tas avec les éléments de t[0 .. n-1] for( i=(n-1)/2; i>=0; i--) // Etape reorganiser(i,n-1); // Phase 2: successivement ranger le plus grand et réorganiser for( imax=n-1; imax>0; imax--) { // Etape aux=t[imax]; t[imax]=t[0]; t[0]=aux; reorganiser(0,imax-1); } } // Réorganise en tas les éléments t[u..v], sachant que t[2*u+1..v] // et t[2*u+2 .. v] sont des tas void reorganiser( int u, int v) { double val; int sc,ifs; // sc:sommet courant, ifs:indice du fils suivant boolean place; val=t[u]; sc=u; place=false; while( 2*sc+1<=v && ! place ) { ifs=2*sc+1; // chercher le plus grand des fils if( ifs+1<=v && t[ifs]<t[ifs+1] ) ifs++; if( val<t[ifs] ) // plus grand fils remonte; sommet courant descend { t[sc]=t[ifs]; sc=ifs; } else place = true; } t[sc]=val; }

6. Tri rapide

void triRapide() { triRapide(0,t.length-1); } // Tri en ordre croissant les éléments t[u .. v] void triRapide(int u, int v) { double aux, val; int p,q; if( u == v-1 ) { // Tableau à 2 éléments: on échange si nécessaire if(t[u] > t[v]) { aux=t[u]; t[u]=t[v]; t[v]=aux; } } else if(u < v) { // Etape: déplacer des éléments de t[u .. v] et chercher // la position p pour y placer val tel que: // si u <= k < p alors: t[k] <= val // si p < k <= v alors: val <= t[k] val=t[u]; p=u; q=v; while( p != q ) { while( p<q && t[p+1]<=val ) p++; while( p<q && t[q]>=val ) q--; if(p < q) { // échange un élément>val et un élément<val aux=t[p+1]; t[p+1]=t[q]; t[q]=aux; p++; q--; } } t[u]=t[p]; t[p]=val; // fin d étape // Trier les sous-tableaux à gauche et à droite de p if(p-u > v-p) { triRapide(u,p-1); triRapide(p+1,v); } else { triRapide(p+1,v); triRapide(u,p-1); } } }

V. Programmation

Ce paragraphe est très différent de ce qui précède; il présente deux exemples de programmation sans aucune préoccupation algorithmique: nous montrons comment trier un tableau d'enregistrements en utilisant le sous-programmme de tri proposé dans le langage; le même traitement est programmé en langage C et en Java. On va voir deux façons différentes d'indiquer la fonction de comparaison.

Dans ces exemples, un enregistrement est constitué par le nom d'un élève, suivi de son age en années et mois au 1er janvier 2002.
Nous présentons deux façons de comparer ces enregistrements. D'une part nous comparons uniquement le nom, ce qui correspond alors à un tri par ordre alphabétique sur le nom. D'autre part nous comparons l'age en mois, et pour des ages identiques, nous classons par ordre alphabétique.

Dans la programmation, nous définissons d'abord la structure d'enregistrement ou de classe utilisés, puis les éléments relatifs aux fonctions de comparaisons et enfin dans une dernière partie (programme principal): définition d'un tableau de valeurs, affichage des données initiales, puis appel des tris et affichage des données triées.

1. Exemple en langage C

Un enregistrement est défini par l'agrégat 'Eleve'; les comparaisons de deux 'Eleve' sont respectivement effectuées par les fonctions cmpNom et cmpAge qui renvoient une valeur négative (resp. nulle ou positive) si le premier Eleve est avant (resp égal ou après) le second.

Dans le programme principal, le tri est effectué par la fonction qsort prenant en paramètres:
        le tableau à trier
        le nombre d'éléments du tableau
        la longueur d'un enregistrement du tableau, en octets
        la fonction de comparaison /* xmp_tri.c */ #include <stdio.h> #include <search.h> /* qsort */ #include <string.h> typedef struct { char nom[30]; int a,m; } Eleve; /*** *** *** *** *** *** *** *** *** *** *** *** *** *** *** *** *** **/ void affEleve(Eleve e) { printf(" %s[%d,%d]",e.nom,e.a,e.m); } void affTabEleve( char txt[], Eleve t[], int n) { int i; printf(txt); for(i=0; i<n; i++) affEleve(t[i]); printf("\n"); } /* Comparaison sur le nom */ int cmpNom( const void *p_e1, const void *p_e2) { Eleve * p1=(Eleve *)p_e1, *p2=(Eleve *)p_e2; return strcmp(p1->nom,p2->nom); } /* Comparaison sur l'age et à égalité d'age, sur le nom */ int cmpAge( const void *p_e1, const void *p_e2) { Eleve * p1=(Eleve *)p_e1, *p2=(Eleve *)p_e2; int a_mois1=12*p1->a+p1->m, a_mois2=12*p2->a+p2->m; int vr; if(a_mois1-a_mois2==0) vr=cmpNom(p_e1,p_e2); else vr=a_mois1-a_mois2; return vr; } void main(int nbm, char* tm[]) { char ligne[1000]; Eleve te[]= { {"Bob",18,5}, {"Zoé",19,12} , {"Sam",18,9}, {"Ali",19,1} , {"Léa", 18,9 }, {"Léo",20,5} , {"Maud",18,5}, {"Jim",19,12} }; int ne= sizeof(te)/sizeof(te[0]); affTabEleve("Données -> ",te,ne); qsort(te,ne,sizeof(te[0]),cmpNom); affTabEleve("Données triées par nom -> ",te,ne); qsort(te,ne,sizeof(te[0]),cmpAge); affTabEleve("Données triées par age -> ",te,ne); }

2. Exemple en langage Java

Un enregistrement est défini par la classe 'Eleve'; les comparaisons de deux 'Eleve' sont définies par les fonctions compare (classes respectives CmpNom et CmpAge) qui renvoient une valeur négative (resp. nulle ou positive) si le premier Eleve est avant (resp égal ou après) le second.

Dans le programme principal, le tri est effectué par la fonction sort de la classe Arrays, prenant en paramètres:
        le tableau à trier
        un objet qui va permettre de préciser la fonction à utiliser pour la comparaison. /* XmpTri.java : exemple de tri*/ import java.util.Comparator; import java.util.Arrays; class Eleve { String nom; int a,m; Eleve(String ch, int an, int mo) {nom=ch; a=an; m=mo; } void aff() { System.out.print(" "+this.nom+" ["+this.a+','+this.m+"]"); } void static void aff(String txt, Eleve t[]) { System.out.print(txt); for(int i=0; i<t.length; i++) t[i].aff(); System.out.println(); } } // Comparaison sur le nom class CmpNom implements Comparator { public int compare( Object obj1, Object obj2) { String nom1= ((Eleve)obj1).nom, nom2=((Eleve)obj2).nom; return nom1.compareTo(nom2); } } // Comparaison sur l'age et à égalité d'age, sur le nom class CmpAge implements Comparator { public int compare( Object obj1, Object obj2) { Eleve e1=(Eleve)obj1, e2=(Eleve)obj2; int a_mois1=12*e1.a+e1.m, a_mois2=12*e2.a+e2.m; int vr; if(a_mois1-a_mois2==0) vr= (new CmpNom()).compare(obj1,obj2); else vr=a_mois1-a_mois2; return vr; } } public class XmpTri { public static void main(String[] args) { // Initialisation d un tableau Eleve te[]= { new Eleve("Bob",18,5), new Eleve("Zoé",19,12) , new Eleve("Sam",18,9), new Eleve("Ali",19,1) , new Eleve("Léa", 18,9), new Eleve("Léo",20,5) , new Eleve("Maud",18,5), new Eleve("Jim", 19,12) }; CmpAge plusJeune = new CmpAge(); Eleve.aff("Données -> ",te); Arrays.sort(te,new CmpNom()); Eleve.aff("Données triées sur le nom -> ",te); Arrays.sort(te,plusJeune); Eleve.aff("Données triées sur l'age -> ",te); } } // fin public class XmpTri // fin XmpTri.java

VI. Conclusion

On a pu réaliser les différences de temps d'exécution suivant la méthode utilisée et la taille des données: pour des tableaux de plusieurs milliers d'éléments, on a un rapport de temps de l'odre de un à mille suivant le tri choisi! dans une situatioin interactive, c'est soit attendre un dixième de seconde, soit attendre cent secondes! Avec un tel ordre de grandeur, on peut affirmer que cette différence ne dépend ni de la façon de programmer, ni du langage utilisé.

D'après les résultats vus ci-dessus, dans une situation réelle, les seuls choix possibles sont les tris arbre ou rapide; si on pense pouvoir rencontrer, sur certaines données le cas défavorable à tri rapide, il faut alors utiliser tri arbre, qui est beaucoup plus régulier quant aux temps d'exécution.

Nous avons vu deux types de méthodes pour traiter un tableau; il est intéressant de les rappeler.
Dans le premier type (tris sélection, insertion et bulle), on a une démarche qu'on peut qualifier de séquentielle: le traitement d'un tableau de taille n se ramène à celui d'un tableau de taille n-1. C'est une démarche relativement facile à comprendre et à mettre en oeuvre.
Dans le deuxième type (tris arbre et rapide) on a vu une démarche arborescente: passer de la taille n à deux sous-tableaux de taille approximativement n/2. On voit tout l'intérêt de la démarche arborescente, plus difficile à comprendre toutefois.

Références

Livres et liens

Un classique
Gaudel, Froixdeveaux, Soria: Types de données et algorithmes
Un classique 'ancien'
Meyer, Baudoin: Méthodes de programmation, Eyrolles
Dans toute bibliothèque
Knuth: the Art of Computer Programmling, Addison Wesley

Quelques adresses sur le Web: