Chapitre 6
Les algorithmes de tri
Dans ce chapitre on présente quelques algorithmes utiles, qui permettent d'ordonner les éléments d'un tableau dans un ordre croissant ou décroissant. L'ordre est par défaut croissant.
Un vecteur est dit trié si V[i] <= V[i+1], quel que soit i Є [1..n-1]
1. Tri par sélection
1-a) Principe
Utiliser un vecteur VT (vecteur trié) comme vecteur résultat. Celui ci contiendra les éléments du vecteur initial dans l'ordre croissant.
Le principe est de :
0- Chercher le plus grand élément dans le vecteur initial V
1- Sélectionner le plus petit élément dans V
2- Le mettre dans son ordre dans le vecteur VT
3- Le remplacer par le plus grand élément dans le vecteur initial (pour qu'il ne sera plus le minimum)
4- Si le nombre d'éléments dans le vecteur résultat n'est pas identique à celui dans le vecteur initial Retourner à l'étape 1 Sinon on s'arrête.
1-b) Exemple
Soit le vecteur V contenant 4 éléments.
V VT
| Au départ | 10 | 15 | -1 | 7 | | | | | |
Phase 1
| 10 | 15 | 15 | 7 | | -1 | | | |
Phase 2
| 10 | 15 | 15 | 15 | | -1 | 7 | | |
Phase 3
| 15 | 15 | 15 | 15 | | -1 | 7 | 10 | |
| Phase 4 | 15 | 15 | 15 | 15 | | -1 | 7 | 10 | 15 |
Schéma de l'algorithme
ALGORITHME TRI_SELECTION
CONST Bi = 1
Bs = 10
VAR V, VT : Tableau[Bi..Bs] de réel
N, i, j, indmin : entier
MIN, MAX : réel
DEBUT
{Chargement du vecteur V}
…
{Recherche du maximum}
MAX¬V[1]
Pour i de 2 à N
FAIRE
Si MAX < V[i] Alors
MAX¬V[i]
FINSI
FINFAIRE
POUR i de 1 à N-1 FAIRE
{Recherche du minimum}
MIN ¬ V[1]
indmin ¬ 1
Pour j de 2 à N faire
Si MIN > V[j] ALORS
MIN¬V[j]
Indmin ¬ j
Fin si
Fin Faire
{Mettre le minimum trouvé à sa place dans le vecteur résultat}
VT[i] ¬ MIN
V[indmin] ¬ MAX
Fin Faire
VT[N] ¬ MAX
FIN
Peut-on améliorer cet algorithme ?
2. Algorithme de tri par sélection et permutation
Il s'agit ici d'éviter la construction d'un second vecteur et d'utiliser un seul vecteur initial qui sera trié.
Supposons traités n-i (1 <= i < N) éléments du vecteur.
V[1..i] non traité V[i+1..N] Trié
1 i N
On peut considérer le vecteur V comme la concaténation de deux sous-vecteurs : le sous-vecteur V[1..i] dont les éléments n'ont pas encore été triés, et le sous vecteur V[i+1..N] dont les éléments sont triés. D'autre part tous les éléments du sous-vecteur V[1..i] sont inférieurs ou égaux à l'élément V[i+1].
On a donc :
V[1..i] non traité, V[1..i] <= V[i+1], V[i+1..N] Trié
On a deux cas :
· I = 1
(V[1] non traité, V[1]<= V[2], V[2..N] trié) donc V[1..N] trié
L'algorithme est terminé.
· I > 1
Pour augmenter le sous-vecteur V[i+1..n] d'un élément, il suffit de chercher le plus grand élément contenu dans le sous-vecteur V[1..i] et de placer cet élément en position i.
Schéma de l'algorithme
ALGORITHME SLECTION_PERMUTATION
CONST Bi = 1
Bs = 10
VAR V : Tableau[Bi..Bs] d'entier
N, i, j : entier
DEBUT
{Chargement du vecteur V}
…
Pour i de N à 2 Faire
{Recherche de l'indice du maximum dans V[1..i]}
indmax ¬ 1
Pour j de 2 à i
FAIRE
Si V[indmax] < V[j] Alors
indmax ¬ i
FIN SI
FIN FAIRE
{Mettre le maximum relatif trouvé à sa place}
Si indmax <> i Alors
Aux ¬ V[indmax]
V[indmax] ¬ V[i]
V[i] ¬ Aux
Fin Si
Fin Faire
3. Tri par la méthode des bulles
Même principe que le précédent.
Après avoir traité n-i (1 <= i < N) éléments du vecteur.
V[1..i] non traité V[i+1..N] Trié
1 i N
On peut donc considérer le vecteur V comme la concaténation de deux sous-vecteurs : le sous-vecteur V[1..i] dont les éléments n'ont pas encore été triés, et le sous vecteur V[i+1..N] dont les éléments sont triés. D'autre part tous les éléments du sous-vecteur V[1..i] sont inférieurs ou égaux à l'élément V[i+1].
On a donc :
V[1..i] non traité, V[1..i] <= V[i+1], V[i+1..N] Trié
On a deux cas :
· I = 1
(V[1] non traité, V[1]<= V[2], V[2..N] trié) donc V[1..N] trié
L'algorithme est terminé.
· I > 1
Pour augmenter le sous-vecteur V[i+1..n] d'un élément, il suffit de chercher le plus grand élément contenu dans le sous-vecteur V[1..i] et de placer cet élément en position i.
On parcourt le sous-vecteur V[1..i] de gauche à droite et, chaque fois qu'il y a deux éléments consécutifs qui ne sont pas dans l'ordre, on les permute. Cette opération permet d'obtenir en fin du iième parcours le plus grand élément placé en position i, et les éléments après cette position sont ordonnés.
Schéma de l'algorithme
ALGORITHME TRI_BULLE1
CONST N= 10
VAR V : tableau[1..N] de réel
N, i, j : entier
AUX : réel
DEBUT
{Chargement du vecteur}
…
POUR i de N à 2 pas –1 FAIRE
POUR j de 1 à i FAIRE
SI V[j]>V[j+1] ALORS
AUX ¬ V[j]
V[j] ¬ V[j+1]
V[j+1] ¬ AUX
FIN SI
FIN FAIRE
FIN FAIRE
FIN
Application
Exécuter à la main cet algorithme avec les vecteurs suivants :
Que remarquez-vous ?
3. Schéma de l'algorithme à bulle optimisé
ALGORITHME TRI_BULLE1
CONST N= 10
VAR V : tableau[1..N] de réel
N, i, j : entier
AUX : réel
DEBUT
{Chargement du vecteur}
…
i ¬ N
atonpermuté ¬ vrai
TANT QUE (atonpermuté) FAIRE
j¬1
atonpermuté ¬ faux
TANT QUE (j < i) FAIRE
DEBUT
SI (V[J+1] < V[j]) ALORS
AUX¬V[J+1]
V[J+1] ¬V[J]
V[J] ¬ AUX
FIN SI
atonpermuté¬vrai
FIN
j¬j+1
FIN
i¬i-1
FIN
FIN
POUR i de N à 2 pas –1 FAIRE
POUR j de 1 à i FAIRE
SI V[j]>V[j+1] ALORS
AUX ¬ V[j]
V[j] ¬ V[j+1]
V[j+1] ¬ AUX
FIN SI
FIN FAIRE
FIN FAIRE
FIN
![V[1..i] non traité](https://www.technologuepro.com/informatique/chap6_algorithme_fichiers/image001.gif){kind=small}
![V[i+1..N] Trié](https://www.technologuepro.com/informatique/chap6_algorithme_fichiers/image002.gif){kind=small}
