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.

Tri par base

Découvreur ou inventeur	Herman Hollerith
Date de découverte	1887
Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(w\cdot n)$

Complexité en espace

Pire cas	$O(w+n)$

Principe

Le principe de l'algorithme est le suivant :

1. On considère le chiffre le moins significatif de chaque clef.
2. 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.
3. 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.

Exemples

Tri d'une liste d'entier

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.

Tri d'un jeu de 52 cartes

Exécution de l'algorithme de tri par base sur un paquet de 52 cartes. (Cliquer pour lancer l'animation)

On peut également utiliser cet algorithme pour trier un jeu de 52 cartes dans l'ordre lexicographique

$1\diamondsuit <2\diamondsuit <...<K\diamondsuit <1\clubsuit <...<K\clubsuit <1\heartsuit <...<K\heartsuit <1\spadesuit <...<Q\spadesuit <K\spadesuit$

obtenu avec l'ordre $1<2<3<4<5<6<7<8<9<10<J<Q<K$ sur les valeurs (nombre ou tête de la carte) et l'ordre $\diamondsuit <\clubsuit <\heartsuit <\spadesuit$ sur les enseignes (ou couleurs).

L'algorithme fonctionne comme suit.

• On prend un paquet de cartes et on fait treize tas pour ranger les cartes en fonction de la valeur de la carte. On obtient donc une pile d'as, de deux et ainsi de suite. On fusionne ensuite ces piles de manière à obtenir un paquet avec les as en premier, puis les deux et ainsi de suite jusqu'aux rois.
• Maintenant, on fait quatre tas pour ranger les cartes en fonctions de leurs couleurs. On pose les cartes sous chaque pile en les posant une à une. Cette opération est stable : les cartes de chaque pile sont triés selon la valeur. On fusionne ensuite les paquets de manière à avoir d'abord les carreaux, puis les trèfles, puis les cœurs et enfin les piques. Le paquet ainsi obtenu est trié dans l'ordre lexicographique.

Pseudo-code

En toute généralité, pour un tableau T d'éléments codés sur $d$ chiffres, l'algorithme de tri par base est :

fonction triParBase(T, d):
   Pour i allant de 1 à d
       Trier avec un tri stable le tableau T selon le i-ème chiffre

Le travail de l'algorithme réside donc dans les algorithmes de tri stable utilisés. Généralement, étant donné que le i-ème chiffre un nombre fini $c_{i}$ de valeurs possibles ordonnées de 1 à $c_{i}$ pour tout $1\leq i\leq d$, on utilise une variante du tri comptage. Après obtention de l'histogramme his des données du tri comptage, on crée un tableau tab de taille $c_{i}$ où, si $1\leq k\leq c_{i}$, tab[k] contient un tableau de taille his[k] des éléments de T rangés par leur ordre d'apparition dans T (ce qui assure la stabilité du tri) tels que leur i-ème chiffre soit à $k$.

Historique

Une trieuse IBM de cartes perforées effectuant un tri par base. On y remarque les treize cases où la machine range les cartes perforées.

Dans le début du XX^e siècle, Herman Hollerith et E.A.Ford ont amélioré l'efficacité des tabulatrices en créant une trieuse automatique de cartes perforées qui repose sur le principe du tri par base. L'opérateur sélectionnait une colonne, puis mettait les cartes perforées dans la trieuse. La trieuse rangeait les cartes dans l'une des treize cases. Les douze premières cases correspondaient aux cartes ayant l'une des douze positions de perforations possibles sur la colonne choisie par l'opérateur, et la treizième case correspondait aux cartes sans perforation sur la colonne. En répétant l'opération autant de fois que de colonnes et en conservant l'ordre de chaque cases, c'est-à-dire en mettant dans la trieuse les cartes de la première case puis celles de la deuxième et ainsi de suite, les cartes perforées étaient triées. En 1923, le tri par base était communément utilisé pour trier les cartes perforées.

En 1954 Harold H. Seward (en) a développé, dans sa thèse de master au MIT, le premier algorithme de tri par base implémenté sur ordinateur. Les algorithmes précédents ne fonctionnaient pas sur ordinateur car ils avaient besoin d'une quantité imprévisible d'espace mémoire en créant un nombre indéterminé de listes de tailles inconnus pour faire les différents tris. L'innovation proposée par Seward était de faire une passe linéaire sur tous les éléments de la liste pour connaître le nombre et la taille des tableaux auxiliaires à créer et d'ensuite appliquer l'algorithme de tri par base en rangeant les éléments dans ces tableaux auxiliaires qui correspondent aux treize cases de sorties des trieuses de Hollerith.

Désormais, le tri par base est appliqué pour trier les chaines de caractères binaire et les entiers. Ce tri est en moyenne plus rapide que les autres algorithmes et est parfois 50% plus rapide ou trois fois plus rapide.

Complexité et caractéristiques

Pour un tableau de taille $n$ d'éléments codés sur $d$ chiffres pouvant prendre $k$ valeurs possibles, le temps d'exécution est en $O(d(n+k))$ si le tri stable employé s'effectue en $O(n+k)$, ce qui est le cas du tri comptage.

De manière générale, si le $i$-ème chiffre peut prendre $k_{i}$ valeurs possibles, la complexité temporelle est en $O\left(nd+\sum _{i=0}^{d}k_{i}\right)$. Par exemple, dans le cas du tri d'un jeu de 52 cartes, on a $k_{1}=13$ et $k_{2}=4$.

Lorsque $d$ est constant et que $k=O(n)$, la complexité en temps du tri par base est linéaire. Ceci est souvent le cas dans le paradigme de la programmation par contrat, où les valeurs de $d$ et $k$ sont fixées à l'avance. Par exemple, c'est le cas lorsqu'on trie par ordre lexicographique des mots de la langue française où $d$ est majoré par 30 et $k$ vaut 42 (nombre de lettres totales dans l'alphabet français en comptant les lettres accentuées). Cela rend ce tri plus rapide que les tris par comparaison (comme les tris rapide, par tas et fusion), qui sont en $\Omega (n\log(n))$.

Le plus grand désavantage du tri par base est qu'il nécessite $O(n)$ espace mémoire supplémentaire et il requiert une analyse de chaque caractère des clefs de la liste d'entrée, il peut donc être très lent pour des clefs longues. Si l'espace mémoire est limité, on préférera employer un tri en place, ce qui diminuera la complexité spatiale mais augmentera la complexité temporelle.

Article connexe

• Tri de nombres entiers

Lien externe

• Démonstration et comparaison du tri par base (en) avec du JavaScript