Un algorithme de tri est un algorithme qui met des éléments d’une liste dans un certain ordre. Les ordres plus utilisées sont l’ordre numérique et l’ordre lexicographique. Un tri efficace est importante pour l’optimisation de l’utilisation d’autres algorithmes (par exemple des algorithmes de recherche et fusion) qui nécessitent des listes triées pour fonctionner correctement ; Il est aussi souvent utile canonicalisation des données et de produire la sortie lisible par l’homme. Plus formellement, la sortie doit satisfaire à deux conditions :
-La sortie est en non décroissante (chaque élément n’est pas plus petit que l’élément précédent selon l’ordre total désiré) ;
-La sortie est une permutation (l’ordre) de l’entrée.
-Tri est l’une des fonctions clés
nécessaire pour de nombreuses applications telles que des décodeurs pour les communications numériques, traitement numérique du signal, VLSI CAD etc.. En conséquence, il y a un intérêt énorme à accélérer de tri dans le logiciel comme matériel.
-Le temps pris dans le tri dépend de nombre de mots dans le cas où des algorithmes logiciels l’amélioration que nous essayons de faire dans ce projet est de rendre les temps dépendant du nombre de bits par mot k et non le nombre de mots
