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 :
- t[0] est le plus grand élément de t[0 .. n-1] ;
- t[0 .. n-2] est aussi un tas (conservation
de la propriété en enlevant le dernier élément);
- 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].
- on commence par déplacer des éléments du tableau,
puis par placer la valeur a à l'indice p, calculé tel que:
tous les éléments d'indice plus petit que p
soient inférieurs à a
tous les éléments d'indice plus grand que p
soient supérieurs à a
La valeur a est alors à sa place définitive dans le tableau
trié
- on refait la même démarche sur chacun des
sous-tableaux t[0 .. p-1] et t[p+1 .. n-1] situés de part
et d'autre de l'indice p.
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élection | Insertion | Bulle | |
Shell | Arbre | Rapide |
640 | |
3.8 | 1.6 | 8.2 | |
0.6 | 0.4 | 0.7 |
6400 | |
329.0 | 138.0 | 873.0 | |
8.8 | 6.1 | 9.6 |
64000 | |
35756.0 | 17698.0 | 96878.0 | |
131.0 | 82.0 | 66.0 |
640000 | |
- - - | - - - | - - - | |
2241.0 | 1235.0 | 824.0 |
Commentaires sur les tableaux aléatoires
- On voit immédiatement que les méthodes élémentaires et intuitives,
Sélection, Insertion et Bulle ne sont pas utilisables
pour des tableaux ayant quelques milliers d'éléments.
- Remarquons, pour ces méthodes, que lorsque la taille est multipliée
par 10, le temps de tri est multiplié par environ 100. Si n
représente la taille, on réalise expérimentalement que le temps de tri
est en O(n2)
- Parmi ces méthodes,
le tri Bulle est mauvais, demandant 96 secondes
pour trier un tableau de taille 64000, alors que le tri Insertion
ne demande que 17 secondes.
- Les méthodes plus élaborées
Shell, Arbre ou Rapide sont à utiliser évidemment. Les temps
obtenus sont semblables, avec un léger handicap pour le tri
Shell. Le tri Rapide est légèrement plus
efficace que les autres pour les grandes tailles.
Ces temps expérimentaux confirment les résultats théoriques:
les méthodes Shell, Arbre ou Rapide ont une complexité en
O(n log2(n) )
- Mais attention, car les performances du tri Rapide
peuvent être très mauvaises quand le tableau à trier est déjà trié !!!
On a mesuré pour tri Rapide exécuté sur des tableaux de 6400
éléments, des temps de:
12 millisecondes pour trier un tableau aléatoire
169 millisecondes pour trier un tableau déjà trié
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élection | Insertion | Bulle | |
Shell | Arbre | Rapide |
640 | |
3.3 | 0.6 | 5.5 | |
0.4 | 0.4 | 0.8 |
6400 | |
351.0 | 22.0 | 588.0 | |
7.1 | 5.5 | 11.0 |
64000 | |
34888.0 | 2802.0 | 65242.0 | |
115.0 | 72.0 | 88.0 |
640000 | |
- - - | - - - | - - - | |
1879.0 | 834.0 | 1143.0 |
Commentaires sur les tableaux presque triés
- Pour le tri Sélection il n'y a aucune différence entre
les temps de tri d'un tableau quelconque ou presque trié. C'est tout
à fait prévisible;
- On constate que le tri Insertion s'adapte à
l'aspect presque trié, car les temps d'exécution sont divisés par
6 environ;
- Le tri Bulle a des temps d'exécution plus petit
pour ces tableaux presque triés, mais le gain est léger: la division est
d'un facteur 1.5 environ;
- Les tris Shell et Rapide ont eux aussi des temps
d'exécution plus petits pour les tableaux presque triés, alors que pour
le tri Rapide le temps d'exécution a tendance à augmenter !
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élection | Insertion | Bulle | |
Shell | Arbre | Rapide |
nb.comparaisons | 640 | |
204480 | 5081 | 203850 | |
4970 | 10033 | 7169 |
6400 | |
20476800 | 72081 | 20472047 | |
92924 | 142426 | 91981 |
nb.lectures | 640 | |
209327 | 105480 | 612354 | |
12961 | 22191 | 9691 |
6400 | |
20532251 | 10314901 | 61223214 | |
229012 | 306223 | 127727 |
nb.ecritures | 640 | |
1278 | 100399 | 204654 | |
7991 | 7180 | 2636 |
6400 | |
127998 | 10242820 | 20279120 | |
136088 | 92987 | 36836 |
Commentaires sur les nombres d'opérations
- On voit immédiatement que pour les méthodes
Sélection et Bulle les nombres de comparaisons sont les
plus élevés. Le Tri insertion effectue par contre un
nombre de comparaisons des plus petits.
- Pour les méthodes Sélection, Insertion et Bulle, les
nombres de comparaisons sont multipliés par environ 100 lorsque la
taille est multipliée par 10. Comme fonction de n , ce nombre
est en O(n2).
- Pour le tri Bulle,les nombres de lectures
sont particulièrement élevés; ce tri n'est donc pas utilisable en
pratique.
- Pour les méthodes Sélection, Insertion et Bulle, les
nombres de lectures sont aussi en
O(n2).
- Les nombres d'écritures sont particulièrement petits pour les
tris Sélection et Rapide; cela se comprend car à chaque
étape de ces tris, un élément est mis à sa place définitive.
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.
Quelques utilisations pour commencer:
- génération de tableau:
En modifiant le choix de taille, on génère à chaque fois
un nouveau tableau; quand la taille dépasse 64, les indices ne sont
pas affichés.
- changement de type de tableau:
En modifiant le choix de type, on change de tableau; voir
la présentation d'un tableau 'trié' ou
'inversé' ou 'presque trié'. Revenir au type
'aléatoire'.
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
-
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.
-
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.
-
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'
-
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.
-
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.
-
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.
Dans cette animation,
- la numérotation des éléments est bicolore, en
noir ou en blanc; les indices en blanc sont les seuls concernés
par cette étape de tri.
- Le but de l'étape est affiché en blanc, puis elle se déroule, ce qui
permet de suivre les modifications des éléments du tableau.
- En fin d'étape:
- une indication est donnée, en deuxième ligne, qui
dépend du tri. Par exemple, pour le tri sélection, est affiché:
'échange entre les éléments d'indice 5 et 15' lorsque lors d'une
étape sur le tableau t[0..15], le maximum a été trouvé à l'indice 5.
- les éléments du tableau intervenant dans une comparaison sont
dessinés en double épaisseur.
- enfin la présentation de l'étape suivante est affichée en troisième
ligne.
- En fin de tri, les nombres d'opérations sont affichés. Le temps
de tri n'est pas affiché car il n'a pas été mesuré.
- Quand le tri est terminé, on peut trier le même tableau, ou un autre
tableau. Si on choisit une méthode de tri (ou la même), il n'y a pas de
génération de nouveau tableau, il est seulement repris dans son état
initial. Si on choisit une taille (ou la même) un nouveau tableau est
généré; il en est de même quand on choisit un type.
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.
- pour commencer:
choisir tri Insertion et voir se dérouler les étapes, après
chaque appui sur 'Une étape'.
- tri Shell :
choisir une taille de 16 et tri Shell, appuyer sur
'Une étape'. On réalise cette notion de sous-tableau ayant
des éléments dont les indices sont incrémentés de 4, en observant les
indices écrits en blanc qui sont seuls concernés dans cette étape
de tri.
En appuyant à nouveau sur 'Une étape', d'autres
éléments sont concernés.
- tri Arbre :
choisir une taille de 16 et tri Arbre, appuyer sur
'Une étape'. Voir le petit nombre d'éléments intervenant
dans chaque tas, pendant la phase 1.
Dans la phase 2, les plus grands éléments successifs sont placés
à droite, comme dans le tri Sélection, mais la
réorganisation en un tas fait intervenir peu d'éléments.
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
- comparaisons entre méthodes:
choisir une taille de 640 et un type de tableau aléatoire.
Effectuer trois tris et comparer le nombre d'opérations:
Commencer par tri Insertion, appuyer sur
'Tri complet'; choisir ensuite tri Bulle et
appuyer sur 'Tri complet'; enfin choisir tri Shell
et appuyer sur 'Tri complet'.
Choisir maintenant l'item Résultats, dans la liste
déroulante située à l'extrême droite. Dans le panneau central,
l'affichage montre pour ces trois tris les nombres d'opérations
effectués, ce qui permet de réaliser le travail maladroit effectué
par tri Bulle.
- divers tableaux soumis à tri Rapide:
revenir par l'item Tri, dans la liste
déroulante située à droite, au panneau de tri.
Choisir la taille de 640 et la méthode tri Rapide;
effectuer un tri complet pour chacun des types de tableau,
respectivement: aléa., trié, inversé et
pr. trié. Faire en plus un tri Sélection sur
le dernier tableau généré.
Repasser à l'affichage des résultats, pour constater d'abord
que les nombres d'opérations varient beaucoup avec le type
du tableau à trier. Remarquer aussi que
tri Rapide fait le même nombre d'opérations que le
tri Sélection quand il travaille sur un tableau inversé;
ce nombre est particulièrement élevé. C'est une faiblesse de
l'algorithme tri Rapide, dont la complexité peut
devenir en O(n2), même si elle est en moyenne
en n log2(n).
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 max) { jmax=j; max=t[jmax]; }
}
// ranger le max: échanger max en t[jmax] et t[aRanger]
t[jmax]=t[aRanger]; t[aRanger]=max;
}
}
Complexité
Le tri se fait en n-1 étapes, pour les valeurs de la variable
aRanger qui sont: n-1, n-2 ... 1.
Le nombre de comparaisons est exactement égal à aRanger, à
chaque étape, soit donc en tout:
(n-1) + (n-2) + ... + 1 = n(n-1)/2
comparaisons
|
Il y a deux écritures dans le tableau t à chaque étape, soit en tout:
Le nombre de lectures dans le tableau est toujours plus élevé que le
nombre de comparaisons, mais ne dépasse pas le double de ce nombre.
2. Tri insertion
void triInsertion() {
double val;
int tst; // taille du sous tableau trié
int j, k, im, n=t.length ;
for( tst=1; tstj; k-- ) t[k+1]=t[k];
t[j+1] = val;
// ici t[0..tst-1,tStTtie] est trié
}
}
Complexité
Le tri se fait en n-1 étapes, pour les valeurs de la variable
tst qui sont successivement: 1, 2 ... n-1.
Le nombre de comparaisons, effectuées lors de la recherche dichotomique
de la position où doit s'insérer val, est au plus égal à
log2(tst), à chaque étape, donc inférieur à
log2(n); donc pour le tri complet on a:
n log2(n)
comparaisons au plus
|
Le nombre d'écritures, effectuées dans la partie 'décalages', est en
moyenne de tst/2 à chaque étape, soit en tout:
(1+2+...n-1)/2 = n(n-1)/4 écritures
|
Le nombre de lectures est égal à la somme du nombre de comparaisons
et du nombre d'écritures, soit environ:
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 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]
}
}
Complexité
Le tri se fait en n-1 étapes, comme pour le tri Insertion.
Le nombre de comparaisons est le même pour les deux tris, soit::
Nombre d'écritures: à chaque échange, il y a deux écritures dans le tableau;
comme il y a en moyenne aRanger/2 échanges par étape, le nombre total
est en moyenne:
2(n-1 + n-2 + ... 1)/2 = n(n-1)/2
écritures
|
Les lectures dans le tableau se font pour chaque comparaison
(2 lectures), et pour chaque échange (2 lectures et 2 écitures). Ce nombre est
donc la somme de 2 fois le nombre de comparaisons et du nombre d'écritures, soit
en moyenne:
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 0; pas /= 3) {
// Etape: Tri des sous-tableaux (éléments distants de pas)
for( i0=0; i0= 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é
}
}
}
}
Pour cet algorithme, l'étude la la complexité dépasse le cadre
de ce texte.
Rappelons simplement que pour les trois opérations comparaison,
écriture et lecture, la complexité au pire du tri Shell
est de l'ordre de n log2(n).
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)
|
Si le premier indice du tableau est 1 (programmation Pascal par exemple),
la relation entre père et fils est alors: le sommet d'indice i a
pour fils gauche, le sommet d'indice 2*i
et pour fils droit, le sommet d'indice 2*i+1.
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]
Pour ce tri arbre, l'arbre partiellement
équilibré plaqué sur le tableau a une hauteur au plus égale à
log2(n). Sans expliciter les démarches d'évaluation, nous
admettons, d'après cette remarque, que les nombres de comparaisons,
écritures et lectures sont au pire en
nlog2(n).
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=val ) q--;
if(p < q) { // échange un élément>val et un élément v-p) { triRapide(u,p-1); triRapide(p+1,v); }
else { triRapide(p+1,v); triRapide(u,p-1); }
}
}
Pour ce tri arbre, la complexité est liée à la taille des sous-tabeaux
à gauche et à droite de l'élément placé. Si en moyenne ces deux sous-tableaux
sont de même taille (ou approximativement), les nombres de
comparaisons ou de lectures seront de l'ordre de
n log2(n).
Par contre si un des sous-tableaux est systématiquement petit par
rapport à l'autre, les nombres de
comparaisons ou de lectures peuvent être de l'ordre de
n2/2.
C'est le cas, par exemple, lorsque le tableau
à trier est ordonné en ordre décroissant, ou en ordre croissant.
La complexité au pire du tri rapide est
n 2;
sa complexité en moyenne est
n log2(n).
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
#include /* qsort */
#include
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; inom,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 ",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: