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 humain peut effectuer cette tâche de manière intuitive. Cependant, un programme informatique doit suivre une séquence d'instructions précises pour y parvenir. Cette séquence d'instructions s'appelle un algorithme. Un algorithme de tri est une méthode qui peut être utilisée pour placer une liste d'éléments 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, qui diffèrent par leur efficacité et leurs performances. Certains algorithmes de tri importants et bien connus sont le tri à bulle, le tri de sélection, le tri par insertion et le tri rapide.
Tri par bulle
L'algorithme de tri par bulle consiste à permuter à plusieurs reprises des éléments adjacents qui ne sont pas présents. ordre jusqu'à ce que toute la liste des articles soit en séquence. De cette manière, les éléments peuvent être considérés comme remontant dans la liste en fonction de leurs valeurs clés.
Le principal avantage du tri à bulle est qu’il est populaire et facile à mettre en œuvre. De plus, dans le tri à bulle, les éléments sont échangés sur place sans utiliser de stockage temporaire supplémentaire, de sorte que l'espace requis est minimal. Le principal inconvénient de ce type de bulle est le fait qu’elle ne traite pas correctement une liste contenant un très grand nombre d’articles. En effet, le tri à bulle nécessite des étapes de traitement au carré pour chaque nombre n d'éléments à trier. En tant que tel, le type à bulle convient principalement à l'enseignement universitaire, mais pas aux applications réelles.
Sciencing Video Vault
Créez le support (presque) parfait: Voici comment créer le support (presque) parfait: Voici comment effectuer un tri de sélection
Le tri de sélection fonctionne en parcourant de manière répétée la liste des éléments, sélectionnant à chaque fois un élément en fonction de son ordre et le plaçant à la bonne position dans la séquence.
L'avantage principal du tri par sélection est qu'il fonctionne bien sur une petite liste. De plus, puisqu'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 de ce type de sélection est sa faible efficacité lors du traitement d’une très grande liste d’articles. Semblable au tri à bulle, le tri de sélection nécessite un nombre d'étages n carré pour trier n éléments. De plus, ses performances sont facilement influencées par la commande initiale des articles avant le processus de tri. De ce fait, le tri de sélection ne convient que pour une liste d'éléments peu nombreux qui sont dans un ordre aléatoire. 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, de sorte que l'espace requis est minimal. L'inconvénient du tri par insertion est qu'il ne fonctionne pas aussi bien que d'autres algorithmes de tri améliorés. Avec des n-carrés requis pour chaque n élément à trier, le tri par insertion ne traite pas bien une liste énorme. Par conséquent, le tri par insertion est particulièrement utile uniquement lors du tri d'une liste d'éléments.
Tri rapide
Le tri rapide fonctionne selon le principe de la division et de la conquête. Tout d’abord, il partitionne la liste d’éléments en deux sous-listes en fonction d’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’organisation est exécuté à plusieurs reprises sur les sous-listes résultantes jusqu’à ce que la liste complète des éléments soit triée.
Le tri rapide est considéré comme le meilleur algorithme de tri. C'est en raison de son avantage considérable en termes d'efficacité car il est capable de gérer une très grande liste d'éléments. Du fait de son tri en place, aucun stockage supplémentaire n'est requis. Le léger inconvénient du tri rapide est que ses performances dans le cas le plus défavorable sont similaires aux performances moyennes des types à bulle, à insertion ou à sélections. En général, le tri rapide constitue la méthode la plus efficace et la plus largement utilisée pour trier une liste de toutes les tailles d’articles.
