Profitez des promotions incroyables de nos cours en pdf!! Ignorer
Un algorithme de tri est un algorithme qui permet d’organiser une collection d’objets selon un ordre déterminé. Il s’agit des ordres numérique et lexicographique (dictionnaire) ou ordre alphabétique. Aussi, l’ordre peut être un ordre croissant ou décroissant :
1 5 2 4 3 1 : pas trié
« Sp » « Zo » « Fan » : aucun tri
1 1 2 3 4 5 : trié en ordre croissant
« Fa » « Sp » « Zo » : tableau de chaine de caractères en ordre croissant
5 4 3 2 1 1 : tableau d’entier en ordre décroissant
« Zo » « Sp » « Fa » : tableau en ordre décroissant
Principe :
– trouver le minimum du tableau
– le placer en tête du tableau (échange (T[1],min))
– recommencer avec le reste du tableau
tableau initial :
99 8 7 1 200 -3 6
-3 8 7 1 200 99 6
-3 1 7 8 200 99 6
-3 1 6 8 200 99 7
-3 1 6 7 200 99 8
-3 1 6 7 8 99 200
-3 1 6 7 8 99 200
Algorithme :
pour i de 1 à n - 1 faire min ←T[i]//initialisation pour j de i +1 à n //Boucle de rechreche du min si T[j] < min alors min ←T[j] //actualisation Fin si FinPour si min <>T[i] alors // échanger (T[i] , min) Fin si Fin Pour |
Remarque:
Une variante consiste à procéder de façon symétrique, en plaçant d’abord le plus grand élément à la fin, puis le second plus grand élément en avant-dernière position, etc.
Exercice : Trier un tableau T(10) en utilisant cette variante
– La partie gauche du tableau contient les données déjà triées
– Pour tout nouvel élément, trouver sa position dans la partie gauche, et l’insérer
2| (5) 1 6 3 10 7 2 5|(1) 6 3 10 7 1 2 5|(6) 3 10 7 1 2 5 6|(3)10 7 1 2 3 5 6|(10)7 1 2 3 5 6 10|(7) 1 2 3 5 6 7 10 | fini
|
( En utilisant une recherche séquentielle)
pour i de 1 à n faire x <-- T[i] j <-- i tant que (j > =2 et T[j - 1] > x ) T[j] <-- T[j - 1] j <-- j – 1 Fin TantQue T[j] <-- x Fin Pour
Remarque:
Le tri par insertion est considéré comme le tri le plus efficace sur des entrées de petite taille. Il est aussi très rapide lorsque les données sont déjà presque triées. Mais ,en général, le tri par insertion est beaucoup plus lent que d’autres algorithmes comme le tri rapide et le tri fusion pour traiter de grandes séquences, car sa complexité asymptotique est quadratique. Pour ces raisons, il est utilisé en pratique en combinaison avec d’autres méthodes comme le tri rapide (ou quicksort).
Exercice : Soit T(10) un tableau des réels. On suppose que le tableau est déjà rempli. Ecrire un algorithme qui permet d’ordonner (trier) le tableau dans l’ordre décroissant en utilisant l’algorithme de tri par insertion
1- on parcourt le tableau en commençant de la fin,
2- on compare l’élément d’indice i avec son voisin immédiat de rang i-1 et on effectue une permutation si l’élément du rang i et inférieur à son voisin du rang i-1.( si t[i]<t[i-1], echange t[i] et t[i-1] )
3- Après chaque parcours complet du tableau, l’algorithme recommence l’opération. Lorsqu’aucun échange n’a lieu pendant un parcours, cela signifie que le tableau est trié. On arrête alors l’algorithme.
A chaque fois, les petites valeurs remontent le tableau (les petites bulles vont vers la surface)
Algorithme :
Repeter AucunEchange<--Vrai Pour j allant de n à 1(-1) Si t[j]<t[j-1] Alors échange(t,j,j-1) AucunEchange<-- faux Finsi FinPour Jusqu’à (AucunEchange=vrai) Fin
Pour conclure, voici un exemple d’un tableau non trié au départ et les étapes de tri selon les trois algorithmes de tri vu dans ce cours (tri par insertion , tri par selection et le tri à bulles) :
Vous pouvez suivre notre liste des vidéos sur l’algorithmique sur notre chaine youtube 9raytifclick (Darija: arabe marocaine) : Cours sur les algorithmes.
Aussi, si vous voulez commencer l’apprentissage d’un langage de programmation, voilà notre cours : Langage Python Niveau 1 qui sera très utile pour vous (il vous aide à pratiquer tous les éléments vu dans notre cours d’algorithmique).
merci beaucoup
Merci beaucoup pour votre cours très bien expliqué. Car je dois avouer que je ne comprenais pas ces trois types de tri, et grace à vous je comprends mieux. Mais comme je ne suis pas hyper douée, je dois continuer à m’entrainer.