Section courante

A propos

Section administrative du site

Introduction

Les algorithmes de tri permettent de mettre en ordre alphabétique ou numérique différents éléments contenu dans un tableau. Voici différents algorithmes en lien avec le tri, comme par exemple : tri à bulles, tri de shell, tri par échange, tri par extraction, tri par insertion, tri sélection, tri QuickSort,...

Tri à bulles

La tri a bulle, mieux connu sous le nom de «Bubble Sort» est habituellement utiliser à des fins d'apprentissage. L'idée derrière cette technique est très simple, parcourir le tableau et permuter deux éléments lorsque cela s'avère nécessaire. En voici son algorithme:

BOUCLE POUR I Nombre d'élément - 2 JUSQU'A 0 PAS -1 FAIRE

BOUCLE POUR J ← 0 JUSQU'A I PAS 1 FAIRE

SI Tableau [ J + 1 ] < Tableau [ J ] ALORS

Échanger Tableau [ J + 1 ] avec Tableau [ J ]

FIN SI

FIN BOUCLE POUR

FIN BOUCLE POUR

Tri de Shell

La technique de tri nommée «Shell-Metzner», est en fait une technique de réduction du nombre de comparaison a effectuer pour trier un tableau. Comment si prend-on? C'est simple, la comparaison s'effectue entre 2 éléments séparer par un écart égal (au départ) à la moitié de la taille du tableau. Ensuite, la comparaison s'effectue entre des éléments séparées par un écart égal au nombre d'élément du tableau divisée par 4. Lorsque l'écart atteint finalement 1, la tri est terminer.

ÉcartNombre d'élément
BOUCLE FAIRE

Écart Écart / 2
BOUCLE FAIRE

Inversion Faux
BOUCLE POUR I ← 1 JUSQU'A Nombre d'élément - Écart

JI + Écart
SI Tableau [ J ] < Tableau [ I ] ALORS

Temporaire Tableau [ I ]
Tableau[I] ← Tableau[J]
Tableau[J] ← Temporaire
Inversion ← Vrai

FIN SI

FIN BOUCLE POUR

TANT QUE N'EST PAS Inversion

TANT QUE Écart = 1

Tri par échange

La technique de tri par échange consiste a comparer un premier élément avec un autre et lorsqu'il trouve un élément plus petit, un échange est effectuer avec ce premier élément. De cette façon, on finira par placer cette élément correctement. Ensuite, on recommence avec le 2ième élément jusqu'à la fin. En voici l'algorithme:

BOUCLE POUR I ← 0 JUSQU'A Nombre d'élément - 2 PAS 1 FAIRE
* Comparer avec les autres éléments.

BOUCLE POUR JI + 1 JUSQU'A Nombre d'élément - 1 PAS 1 FAIRE

SI Tableau [ I ] > Tableau [ J ] ALORS

Échanger Tableau [ J ] avec Tableau [ I ]

FIN SI

FIN BOUCLE POUR

FIN BOUCLE POUR

Tri par extraction

La tri par extraction est une consiste a tout d'abord trouver le plus élément d'un tableau et de l'échanger avec le premier indice de celui, soit habituellement l'indice 0. Par la suite, il poursuit ses recherches d'un élément minimum entre l'élément 1 à celle de la fin. Il effectuera se traitement jusqu'à terme. Voici donc l'algorithme:

BOUCLE POUR K ← 0 JUSQU'A Nombre d'élément - 2 PAS 1 FAIRE

Position MinimumK

BOUCLE POUR JK + 1 JUSQU'A N – 1

SI Tableau [ J ] < Tableau [ Position Minimum] ALORS Position MinimumJ

BOUCLE FIN POUR

SI Position Minimum <> K ALORS

Échanger Tableau[K] avec Tableau[Position Minimum]

FIN SI

FIN BOUCLE POUR

Tri par insertion

La tri par insertion comme son nom l'indique consiste à prendre le premier élément en commençant par le deuxième et d'ensuite de l'insérer directement à la place approprié dans les indices situés entre 0 et I. Voici donc son algorithme:

BOUCLE POUR I ← 1 JUSQU'A Nombre d'élément - 1 PAS 1 FAIRE

BOUCLE POUR J ← 0 JUSQU'A I - 1 PAS 1 FAIRE

SI Tableau [ I ] <= Tableau [ J ] ALORS

Temporaire Tableau [ I ] * L'élément à insérer
BOUCLE POUR K I - 1 JUSQU'A J PAS -1 FAIRE * Faire de la place.

Tableau [ K + 1 ] ← Tableau [ K ]

FIN POUR
Tableau [ J ] ← Temporaire * Insère l'élément.
QUITTER BOUCLE * Fin de la deuxième boucle.

FIN SI

FIN BOUCLE POUR

FIN BOUCLE POUR

Tri sélection

La tri par sélection est une technique très intéressante, en effet, contrairement à la Tri à bulles ou par échanges, elle sélectionne systématiquement le plus petit élément et échange celui-ci avec le premier élément de la liste. Ensuite, il applique cette même manière de procéder avec le 2ième élément jusqu'à la fin de la liste. En voici l'algorithme:

BOUCLE POUR I ← 0 JUSQU'A Nombre d'élément - 2 PAS 1 FAIRE

PositionI
TemporaireTableau [ I ]
* Chercher le plus petit élément à partir de la position «I»
BOUCLE POUR JI + 1 JUSQU'A Nombre d'élément - 1 PAS 1 FAIRE

SI Tableau [ J ] < Temporaire ALORS

PositionJ
TemporaireTableau [ J ]

FIN SI

FIN BOUCLE POUR
* Mettre le plus petit élément à la position «I»
Tableau [ Position ] ← Tableau [ I ]
Tableau [ I ] ← Temporaire

FIN BOUCLE POUR

Tri par QuickSort

Le «QuickSort» est sans nulle doute la technique de tri la plus rapide. Le seul inconvénient de cette technique c'est qu'elle empile un grand nombre d'élément dans la pile, on ne pourra donc pas l'employer par exemple pour une base de données sollicitant des millions d'informations. Toutefois, elle pourra être utilise en graphisme par exemple. Voici l'algorithme de cette technique de tri:

MODULE QuickSort ( référence A,valeur L,valeur R )

IL

JR

XA [ ( L + R ) / 2 ]

BOUCLE FAIRE TANT QUE I < J

BOUCLE FAIRE TANT QUE A [ I ] < X

II + 1

FIN BOUCLE TANT QUE

BOUCLE FAIRE TANT QUE X < A [ J ]

JJ + 1

FIN BOUCLE TANT QUE

SI I <= J ALORS

Échange A [ I ] et A [ J ]

II + 1

JJ + 1

FIN SI

FIN BOUCLE TANT QUE

SI L < J ALORS

QuickSort( A, L, J )

FIN SI

SI I < R ALORS

QuickSort ( A, I, R )

FIN SI



Dernière mise à jour : Dimanche, le 12 mars 2006