Qu'est-ce que le tri en tableau?
Le tri par tableau consiste à prendre les différents éléments d'un tableau et à les organiser dans un type d'ordre logique en fonction d'une série de règles définies par l'utilisateur. Le processus implique de parcourir le tableau, un élément à la fois, et de tester cet élément par rapport aux éléments environnants pour déterminer s'il doit être déplacé vers un autre index du tableau. Lorsque vous effectuez un tri matriciel, vous pouvez utiliser plusieurs algorithmes, notamment lorsque les conditions de tri sont numériques et non plus arbitraires. La plupart des algorithmes de tri de matrices sont mesurés par leur vitesse et leur efficacité, les algorithmes les plus lents étant les plus faciles à programmer et les plus rapides beaucoup plus complexes.
L'algorithme de tri de matrice le plus simple s'appelle une sorte de bulle, et c'est aussi le plus lent. Le processus commence par une boucle qui parcourt chaque élément du tableau. L'élément en cours est comparé à l'élément suivant du tableau et, si l'élément suivant a une valeur inférieure à celle de l'élément en cours, les données des index sont commutées. L'inconvénient d'un tri à bulle est qu'il doit parcourir plusieurs fois le tableau pour effectuer tous les échanges nécessaires pour trier le tableau. Dans les implémentations les plus élémentaires, le tri parcourt l'intégralité du tableau une fois pour chaque élément qu'il contient.
Un tri par sélection utilise un algorithme qui effectue le tri d'un tableau de manière légèrement plus efficace qu'un tri à bulle, mais nécessite néanmoins plusieurs itérations à travers le tableau. Ce tri commence par une boucle dans le tableau pour trouver l'élément dont la valeur est la plus basse. Cet élément est ensuite placé dans le premier index du tableau et certaines variables de suivi sont incrémentées. Le cycle se répète ensuite, recherchant maintenant la valeur la plus basse suivante qui sera ensuite placée dans le deuxième index du tableau. Le processus se poursuit jusqu'à ce que l'élément de valeur la plus élevée soit placé dans le dernier index du tableau.
Une méthode de tri de matrice qui peut être efficace mais parfois complexe à mettre en œuvre est connue sous le nom de tri rapide. Le tri rapide consiste à prendre une valeur située au milieu de toutes les valeurs possibles contenues dans le tableau. L'algorithme parcourt tous les éléments du tableau et place toutes les valeurs supérieures au nombre médian à la fin du tableau et les valeurs inférieures au début. Ce processus est exécuté de manière récursive sur des blocs du tableau jusqu'à ce que, à la fin, tout le tableau soit trié. En supposant que la valeur moyenne utilisée pour le tableau soit assez précise, cela peut être un moyen très rapide de trier.
Un facteur qui peut affecter un algorithme de tri de matrice est le moyen par lequel les données sont testées pour vérifier leur équivalence. Il est facile de comparer des nombres simples pour lesquels la valeur est supérieure, mais cela pourrait ne pas être le cas pour des classes de données complexes dans lesquelles plusieurs conditions doivent être comparées. Plus il est long de comparer si un élément est supérieur ou inférieur à un autre, plus il faudra de temps à l'algorithme pour trier le tableau.