Tri par base

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.

En toute généralité, pour un tableau T d'éléments codés sur ${\displaystyle d}$ chiffres, l'algorithme de tri par base[2] 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 ${\displaystyle c_{i}}$ de valeurs possibles ordonnées de 1 à ${\displaystyle c_{i}}$ pour tout ${\displaystyle 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 ${\displaystyle c_{i}}$ où, si ${\displaystyle 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 à ${\displaystyle k}$.

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[3]. 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[1].

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[1]. 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[4] - [5] - [6].

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

De manière générale, si le ${\displaystyle i}$-ème chiffre peut prendre ${\displaystyle k_{i}}$ valeurs possibles, la complexité temporelle est en ${\displaystyle 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 ${\displaystyle k_{1}=13}$ et ${\displaystyle k_{2}=4}$.

Lorsque ${\displaystyle d}$ est constant et que ${\displaystyle k=O(n)}$, la complexité en temps du tri par base est linéaire[2]. Ceci est souvent le cas dans le paradigme de la programmation par contrat, où les valeurs de ${\displaystyle d}$ et ${\displaystyle 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ù ${\displaystyle d}$ est majoré par 30 et ${\displaystyle 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 ${\displaystyle \Omega (n\log(n))}$[1].

Le plus grand désavantage du tri par base est qu'il nécessite ${\displaystyle 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[2].

• Tri de nombres entiers

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