Tri par base

En algorithmique le tri par base, ou tri radix de radix sort en anglais, est un algorithme de tri, utilisé pour ordonner des éléments identifiés par une clef unique. Chaque clef est une chaîne de caractères ou un nombre que le tri par base trie selon l'ordre lexicographique. Cet algorithme a besoin d'être couplé avec un ou plusieurs algorithmes de tri stable. Le principe de l'algorithme est le suivant : On considère le chiffre le moins significatif de chaque clef. On trie la liste des éléments selon ce chiffre avec un algorithme de tri stable. Il y a une conservation de l'ordre des éléments ayant le même chiffre car le tri est stable. On répète l'étape 2 en regardant le chiffre suivant. Comme on le verra dans les exemples, un chiffre peut être une valeur d'une carte, une couleur d'une carte, un chiffre dans l'écriture décimale d'un nombre, un bit ou un groupe de bits. Nous allons utiliser cet algorithme pour trier par ordre croissant la liste : 170, 45, 75, 90, 2, 24, 802, 66. Ici, le chiffre le moins significatif est le chiffre des unités, ensuite celui des dizaines et enfin celui des centaines. L'algorithme fonctionne comme suit. On commence par trier la liste par ordre croissant du chiffre des unités. On obtient : 170, 90, 2, 802, 24, 45, 75, 66. On trie la liste obtenue en triant par ordre croissant du chiffre des dizaines en utilisant un tri stable. On obtient : 2, 802, 24, 45, 66, 170, 75, 90. Ici 170 est avant 75 car on a utilisé un tri stable qui par définition ne modifie pas l'ordre initial des nombres ayant une clé identique, ici le chiffre des dizaines 7. On trie cette nouvelle liste en triant par ordre croissant du chiffre des centaines en utilisant un tri stable. On obtient alors la liste triée 2, 24, 45, 66, 75, 90, 170, 802. Les nombres de 2 à 90 n'ont pas de chiffre des centaines, on ne change donc pas la position obtenue précédemment. vignette|330x330px|Exécution de l'algorithme de tri par base sur un paquet de 52 cartes.