Abstrait

Solution matérielle aux algorithmes de tri : une analyse

Rouf Ali

Les algorithmes de tri réorganisent les éléments de données d'un tableau ou d'une liste de données dans un certain ordre, soit par ordre croissant, soit par ordre décroissant pour les données numériques, par ordre alphabétique pour les données de type caractère et par ordre chronologique pour le type de données de date. Il existe plusieurs applications de programmation utilisées en informatique qui appliquent des techniques de tri. Il existe deux types d'algorithmes de tri. Les algorithmes basés sur la comparaison et les algorithmes non basés sur la comparaison. Dans un algorithme de tri basé sur la comparaison, les éléments d'un tableau sont comparés les uns aux autres pour déterminer lequel des deux éléments doit apparaître en premier dans la liste triée finale. Les meilleurs algorithmes de tri basés sur la comparaison ont une limite inférieure de complexité de n log n. Les algorithmes de tri basés sur la comparaison ne font aucune hypothèse sur l'entrée et peuvent traiter n'importe quel cas d'entrée. Les algorithmes non basés sur la comparaison utilisent la nature des éléments de données de la liste pour effectuer le tri. Leurs algorithmes de tri utilisent des informations spéciales sur les clés (valeurs/éléments/éléments) et des opérations autres que la comparaison pour déterminer l'ordre de tri des éléments. Par conséquent, la limite inférieure n log n ne s'applique pas à ces algorithmes de tri. Les algorithmes non basés sur la comparaison s'exécutent en temps linéaire et nécessitent des hypothèses particulières sur la séquence d'entrée à trier.