Définition :

Un algorithme de tri est un algorithme qui permet d'ordonner des listes d'objets selon  un ordre déterminé, croissant ou décroissant :

  1. Ordre croissant : Un tableau t est dit trié en ordre croissant si pour tout indice i<j, t[i]<=t[j]
  2. Ordre décroissant : Un tableau trié en ordre décroissant  veut dire que pour tout indice i<j, t[i]>=t[j]
exemple:
tableau non trié :
ntr
tableau trié en ordre croissant :
cr
tableau trié en ordre décroissant :
dec
1- Algorithme de tri par sélection :
Principe :
Aller chercher le plus petit élément du vecteur pour le mettre en premier, puis de repartir du second, d'aller chercher le plus petit élément pour le mettre en second etc.
Dans le  i ème itération, on sélectionne l’élément ayant la plus petite valeur parmi les positions i..n et on l'échange avec T[i].
L'algorithme:
version 1:
Procedure tri_selection(var t:tableau)
var 
i,j,n,m,temp: entier;
Debut
pour  i ← 1  à n  - 1 faire
   m  ←i;
   pour  j ← i +1  à n     
         si T[j] <  t[m]      alors
         m ←j
         temp←t[i];
         t[i]←t[m];
         t[m]←temp;
         Fin si
   FinPour

Fin  Pour
fin;
version 2:
Procedure tri_selection(var t:tableau)
var 
i,j,n,m : entier;
Debut
pour  i ← 1  à n  - 1 faire
m  ←i
   pour  j ← i +1  à n     
         si T[j] <t[m]      alors
         m ←j
         Fin si
   FinPour
temp←t[i];
t[i]←t[m];
t[m]←temp;
FinPour
fin;
exemple :
tableau T:

t
l'application de l'algorithme de tri par sélection :
tt

Last modified: Saturday, 15 January 2022, 8:30 AM