Contenu
La commande d'un ensemble d'articles dans une liste est une tâche fréquente en programmation. Souvent, un être humain peut effectuer cette tâche de manière intuitive. Cependant, un programme informatique doit suivre une séquence exacte d'instructions pour le terminer, et cette séquence est appelée un algorithme. Un algorithme de classement est une méthode utilisée pour placer une liste d'éléments désorganisés dans un ordre donné. La séquence de commande est déterminée par une clé. Il existe plusieurs algorithmes de tri qui diffèrent en termes d'efficacité et de performances. Certains connus et importants de ce type incluent: le tri à bulles, le tri par sélection, le tri par insertion et le tri rapide.
Tri à bulles
Le tri à bulles échange à plusieurs reprises les éléments adjacents qui ne sont pas dans l'ordre tant que la liste entière des éléments n'est pas en séquence. De cette façon, les éléments flottent dans la liste en fonction de leurs valeurs, le plus grand (dans le cas d'un tri croissant) allant à la fin à la fin de chaque itération.
Le principal avantage de cet algorithme est que sa mise en œuvre est simple et connue. De plus, dans le tri à bulles, les éléments sont changés de place sans utiliser de stockage temporaire, ce qui rend l'encombrement minimal. Le principal inconvénient est le fait qu'il ne montre pas de bons résultats lorsque la liste contient de nombreux éléments. En effet, ce type de tri nécessite n² étapes de traitement pour chaque n nombre d'éléments qui seront triés. Par conséquent, le tri à bulles convient à l'enseignement universitaire, mais pas aux applications réelles.
Tri de sélection
Le tri par sélection recherche à plusieurs reprises la liste des éléments, en sélectionnant un élément à la fois et en le plaçant à la bonne position dans la séquence.
Le principal avantage du tri par sélection est qu'il fonctionne bien sur une courte liste. De plus, comme il s'agit d'un algorithme de classement des lieux, il n'a pas besoin de stockage temporaire au-delà de ce qui est nécessaire pour stocker la liste d'origine. Le principal inconvénient est sa faible efficacité sur les grandes listes. Comme le tri à bulles, il nécessite n² d'étapes pour chaque n éléments. De plus, ses performances sont facilement influencées par l'ordre initial des éléments avant le processus de tri. Pour cette raison, ce type de sélection ne convient que pour une liste où peu d'éléments sont dans un ordre aléatoire.
Tri par insertion
Le tri par insertion analyse la liste à plusieurs reprises et, à chaque fois, insère un élément de la séquence désordonnée dans la position correcte.
Le principal avantage du tri par insertion est sa simplicité, en plus de montrer de bonnes performances dans les petites listes. C'est un algorithme de commande de place, donc l'espace requis est minime. L'inconvénient est qu'il ne fonctionne pas aussi bien que les autres algorithmes de tri. Avec n² étapes nécessaires pour fonctionner, le tri par insertion ne fonctionne pas non plus correctement avec de grandes listes. Cependant, il est particulièrement utile avec des listes de quelques éléments.
Tri rapide
Le tri rapide fonctionne sur le principe de la division et de la conquête. Tout d'abord, il divise la liste d'éléments en deux sous-listes basées sur un élément pivot. Tous les éléments de la première sous-liste sont agencés de sorte qu'ils soient plus petits que le pivot, tandis que tous les éléments de la seconde sous-liste sont agencés pour être plus grands que le pivot. Le même processus de partitionnement et d'organisation est exécuté à plusieurs reprises sur les sous-listes résultantes jusqu'à ce que la liste entière soit organisée.
Le tri rapide est considéré par certains comme le meilleur algorithme de tri en raison de son avantage d'efficacité significatif, car il fonctionne bien avec une grande liste d'éléments. En commandant sur place, il n'y a pas non plus besoin d'espace de stockage supplémentaire. Le léger inconvénient qu'il présente est que ses pires performances sont similaires aux performances moyennes des autres algorithmes décrits ci-dessus. Cependant, il est important de noter que ce pire des cas est très rare. Plus généralement, le tri rapide produit la méthode la plus efficace et la plus largement utilisée pour organiser une liste de toute taille.
