les algorithmes de tri
متطلبات الإكمال
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 :
- Ordre croissant : Un tableau t est dit trié en ordre croissant si pour tout indice i<j, t[i]<=t[j]
- Ordre décroissant : Un tableau trié en ordre décroissant veut dire que pour tout indice i<j, t[i]>=t[j]
tableau non trié :
tableau trié en ordre croissant :
tableau trié en ordre décroissant :
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; |
| 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; |
tableau T:
l'application de l'algorithme de tri par sélection :
آخر تعديل: السبت، 15 يناير 2022، 8:30 AM