Expose Algorithme
• Membre groupe
LOMPO DIASSIBO
BIRBA EMMANUEL
COMBARY LIONNEL
COMPAORE JEAN
DICKO AMADOU
THEME : ALGORITHME DE TRI D’UN TABLEAU : CAS DE TRI
PAR SELECTION
I. INTRODUCTION
II. TRI PAR SELECTION
[Link] propriétés de tri par sélection
[Link] Principes de tri par sélection
V. Exemples de tri par sélection :
Tri par sélection du minimum
Tri par sélection du maximum
[Link]
I. INTRODUCTION
• Un algorithme de tri est un algorithme qui permet d’organiser une collection
d’objets selon un ordre déterminé.
• Les objets à trier font partie d’un ensemble muni d’une relation d’ordre. Les
ordres les plus utilisés sont l’ordre numérique et l’ordre lexicographique.
• Un tableau d’entier t est dit trié en ordre croissant si pour tout indice i<j,
t[i]<=t[j] (trie en ordre croissant :1 1 2 3 4 5).
• Un tableau d’entier t est dit trié en ordre décroissant si pour tout indice i>j,
t[i]>=t[j] (trie en ordre décroissant :5 4 3 2 1 1).
• Il existe plusieurs algorithmes de tri permettant de trier un tableau : tri par
sélection, par insertion, par bulle, par fusion, rapide, et par TAS, … (ils ont tous
leurs points forts et leurs points faibles, ainsi un algorithme sera lent, et
l’autre gourmand en mémoire et ainsi de suite...). Cependant, nous
n’étudierons que le tri par sélection.
II. TRI PAR SELECTION
• Le tri par sélection ou tri par extraction est un algorithme de tri par
comparaison. Il est sans doute le tri le plus simple à imaginer.
[Link] PROPRIÉTÉS DE TRI PAR SÉLECTION
•Le tri par sélection est un tri en place (les éléments sont triés directement dans la
structure). Ce n’est pas un tri stable (l’ordre d’apparition des éléments égaux n’est pas
réservé).
• Toutefois, si l’on travaille sur une structure de données adaptées (typiquement une
liste), il est facile de le rendre stable : à chaque itération, il convient de chercher la
première occurrence de l’élément le plus petit de la partie non triée de la liste, et de
l’insérer avant le premier élément de la partie non triée de la liste, plutôt que de
l’échanger avec celui-ci.
• Implémentée sur un tableau, cette modification implique de décaler toute une
partie du tableau à chaque itération, et n’est donc intéressant.
[Link] PRINCIPES DE TRI PAR
SÉLECTION
• Rechercher le plus petit élément du tableau et l’échanger avec le
premier élément
• Rechercher le plus petit élément entre les positions 2 et n-1 et l’échange
avec le deuxième élément
• Poursuivre ainsi jusqu’à l’avant dernier élément de la liste et pour
chaque position, la partie d’indices inférieurs est déjà triée, on
recherche juste le minimum de la partie de la liste d’indices supérieurs
(c’est -à- dire la partie de droite de notre liste).
V. EXEMPLES DE TRI PAR SÉLECTION :
Tri par sélection du minimum
Principe :
• Trouver le minimum du tableau
• Le placer en tête du tableau (échange (T [1], min))
• Recommencer avec le reste du tableau
V. EXEMPLES DE TRI PAR SÉLECTION :
Tri par sélection du minimum
Exemple : tableau initial :
I 1 2 3 4 5
T[i] 4 0 5 -8 5
Algorithme sélection :
Itération 1
imin= 4 I 1 2 3 4 5
T[i] -8 0 5 4 5
min= -8
on échange T[1] avec T[4]
V. EXEMPLES DE TRI PAR SÉLECTION :
Tri par sélection du minimum
Exemple : tableau initial : I 1 2 3 4 5
T[i] -8 0 5 4 5
Itération 2 I 1 2 3 4 5
T[i] -8 0 5 4 5
V. EXEMPLES DE TRI PAR SÉLECTION :
Tri par sélection du minimum
Exemple : tableau initial : I 1 2 3 4 5
T[i] -8 0 5 4 5
Itération 3 I 1 2 3 4 5
T[i] -8 0 4 5 5
V. EXEMPLES DE TRI PAR SÉLECTION :
Tri par sélection du minimum
Exemple : tableau initial :
I 1 2 3 4 5
T[i] -8 0 4 5 5
Itération 4 I 1 2 3 4 5
T[i] -8 0 4 5 5
Après l’itération 4 : i 1 2 3 4 5
T[i] -8 0 4 5 5
V. EXEMPLES DE TRI PAR SÉLECTION :
•
•ALGORITHME tri-sélection
• CONST NBMAX ←5: entier ;
• VAR : i, j, min, imin, n,tmp :entier ;
• T : TABLEAU [NBMAX] D’entier ;
•DEBUT
• Pour i de 1 à n-1 faire
• min←T[i] ;
• imin←i ;
• Pour j de i+1 à n faire
• SI T[j]<min alors
• min←T[j] ;
• imin←j ; }cette boucle recherche l’indice du
minimum.
• FINSI
• Fin pour
• tmp←T[i] ;
• T[i]←T[imin]
V. EXEMPLES DE TRI PAR SÉLECTION :
Tri par sélection du maximum
Principe :
• Trouver le maximum du tableau
• Le placer en tête du tableau (échange (T [1], max))
• Recommencer avec le reste du tableau
V. EXEMPLES DE TRI PAR SÉLECTION :
•ALGORITHME tri-sélection
• CONST NBMAX ←5: entier ;
• VAR : i, j, max, imax, n,tmp : entier ;
• T : TABLEAU [NBMAX] D’entier ;
•DEBUT
• Pour i de 1 à n-1 faire
• max←T[i] ;
• imax←i ;
• Pour j de i+1 à n faire
• SI T[j]>max alors
• max←T[j] ;
• imax←j ; }cette boucle recherche l’indice du
maximum.
• FINSI
• Fin pour
• tmp←T[i] ;
• T[i]←T[imax] ;
• T[imax]←tmp ;
• Fin pour
VI. CONCLUSION
•
Parmi les différents algorithmes de tri, le tri par sélection ne fonctionne
efficacement que lorsque le petit ensemble d’éléments est impliqué ou que la liste est
partiellement triée au préalable. Le nombre de comparaisons faites par le tri par sélection est
supérieur aux mouvements effectués. Semblable au tri à bulles, le tri de sélection nécessite
un nombre n de carrés d’étapes pour trier n éléments. De plus, ses performances sont
facilement influencées par la commande initiale des articles avant le processus de tri.
Source : Wikipédia