Tri par insertion:
Le tri par insertion fonctionne en insérant l’ensemble de valeurs dans le fichier trié existant.
Il construit le tableau trié en insérant un seul élément à la fois. Ce processus se poursuit jusqu’à ce que le
tableau entier soit trié dans un certain ordre. Le concept principal du tri par insertion consiste à insérer
chaque élément à l’endroit approprié dans la liste finale. La méthode de tri par insertion permet
d’économiser une quantité efficace de mémoire.
Avantages du tri par insertion:
· Facilement mis en œuvre et très efficace lorsqu’il est utilisé avec de petits ensembles de
données.
· L’espace mémoire supplémentaire requis pour le tri par insertion est inférieur (c’est-à-dire O (1)).
· Il est considéré comme une technique de tri en direct car la liste peut être triée lorsque les
nouveaux éléments sont reçus.
· C’est plus rapide que les autres algorithmes de tri.
Tri par fusion:
Le tri par fusion est un algorithme récursif et la complexité temporelle peut être exprimée comme une
relation de récurrence.
Le principe:
1. Diviser : diviser la liste de N éléments à trier en deux sous-listes de N/2 éléments
2. Régner : trier les deux sous-listes récursivement à l’aide du tri par fusion
3. Combiner : fusionner les deux sous-listes triées pour produire la réponse triée
Tri rapide:
Cet algorithme appelé ALGORITHME TRI RAPIDE (QuickSort), il s'agit d'ordonner le tableau à partir d'un
pivot (valeur choisie dans le tableau (généralement la première valeur). Dans ce mêmetableau on classe
à gauche les valeurs inférieurs et à droite les valeurs supérieurs. Ensuite on rappelle l'ALGORIHTME TRI
RAPIDE, une fois pour la partie gauche, une fois pour la partie droite.
Avantages et inconvénients:
Il possède un bon comportement de cas moyen. La complexité du tri rapide est complexe, car elle est
plus rapide que des algorithmes tels que le tri à bulle, le tri par insertion et le tri par sélection.
Cependant, il est complexe et très récursif, c’est la raison pour laquelle il n’est pas adapté aux grands
tableaux.
