Le tri d'un ensemble d'éléments dans une liste est une tâche qui se produit souvent dans la programmation informatique. Souvent, un être humain peut effectuer cette tâche de manière intuitive. Cependant, un programme informatique doit suivre une séquence d'instructions exactes pour ce faire. Cette séquence d'instructions est appelée algorithme. Un algorithme de tri est une méthode qui peut être utilisée pour placer une liste d'articles non ordonnés dans une séquence ordonnée. La séquence de commande est déterminée par une clé. Il existe différents algorithmes de tri, et ils diffèrent en termes d'efficacité et de performances. Certains algorithmes de tri importants et bien connus sont le tri à bulles, le tri par sélection, le tri par insertion et le tri rapide.
Tri par bulles
L'algorithme de tri par bulles fonctionne en échangeant à plusieurs reprises les éléments adjacents qui ne sont pas dans commander jusqu'à ce que la liste complète des articles soit en séquence. De cette façon, les éléments peuvent être considérés comme remontant la liste en fonction de leurs valeurs clés.
Le principal avantage du tri à bulles est qu'il est populaire et facile à mettre en œuvre. De plus, dans le tri à bulles, les éléments sont échangés en place sans utiliser de stockage temporaire supplémentaire, de sorte que l'espace requis est au minimum. Le principal inconvénient du tri à bulles est le fait qu'il ne gère pas bien une liste contenant un grand nombre d'articles. En effet, le tri à bulles nécessite des étapes de traitement n au carré pour chaque nombre n d'éléments à trier. En tant que tel, le tri à bulles convient principalement à l'enseignement universitaire, mais pas aux applications réelles. à son ordre et à le placer dans la bonne position dans la séquence.
Le principal avantage du tri par sélection est qu'il fonctionne bien sur une petite liste. De plus, comme il s'agit d'un algorithme de tri sur place, aucun stockage temporaire supplémentaire n'est requis au-delà de ce qui est nécessaire pour conserver la liste d'origine. Le principal inconvénient du tri par sélection est sa faible efficacité lorsqu'il s'agit d'une énorme liste d'articles. Semblable au tri à bulles, le tri par sélection nécessite un nombre n de carrés d'étapes pour trier n éléments. De plus, ses performances sont facilement influencées par la commande initiale des articles avant le processus de tri. Pour cette raison, le tri de sélection ne convient qu'à une liste de quelques éléments qui sont dans un ordre aléatoire.
Tri par insertion
Le tri par insertion balaye à plusieurs reprises la liste des éléments, chaque fois en insérant l'élément dans le séquence non ordonnée dans sa position correcte.
Le principal avantage du tri par insertion est sa simplicité. Il présente également une bonne performance lorsqu'il s'agit d'une petite liste. Le tri par insertion est un algorithme de tri sur place, donc l'espace requis est minimal. L'inconvénient du tri par insertion est qu'il ne fonctionne pas aussi bien que d'autres meilleurs algorithmes de tri. Avec n étapes au carré requises pour chaque élément n à trier, le tri par insertion ne gère pas bien une énorme liste. Par conséquent, le tri par insertion n'est particulièrement utile que lors du tri d'une liste de quelques éléments.
Tri rapide
Le tri rapide fonctionne selon le principe de division et de conquête. Tout d'abord, il partitionne la liste des é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 pour être plus petits que le pivot, tandis que tous les éléments de la deuxième sous-liste sont agencés pour être plus grands que le pivot. Le même processus de partitionnement et d'arrangement est effectué à plusieurs reprises sur les sous-listes résultantes jusqu'à ce que toute la liste des éléments soit triée.
Le tri rapide est considéré comme le meilleur algorithme de tri. Cela est dû à son avantage significatif en termes d'efficacité car il est capable de bien gérer une énorme liste d'articles. Parce qu'il trie sur place, aucun stockage supplémentaire n'est également requis. Le léger inconvénient du tri rapide est que ses performances dans le pire des cas sont similaires aux performances moyennes des types de bulles, d'insertion ou de sélections. En général, le tri rapide produit la méthode la plus efficace et la plus utilisée pour trier une liste de n'importe quelle taille d'élément.
