En informatique, le tri de nombres entiers est le problème algorithmique consistant à trier une collection d'éléments au moyen de clés numériques, chacune étant un nombre entier. Les algorithmes conçus pour le tri des nombres entiers peuvent également souvent être appliqués aux problèmes de tri dans lesquels les clés sont des nombres décimaux, des nombres rationnels ou des chaînes de texteHan & Thorup (2002).
La possibilité d'effectuer une arithmétique sur les clés permet aux algorithmes de tri d'entiers d'être plus rapides que les algorithmes de tri par comparaison, en fonction du détail des opérations autorisées dans le modèle de calcul et de la taille des entiers à trier.
Les algorithmes de tri de nombres entiers, notamment le tri par paquets, le tri comptage et le tri par base, sont largement utilisés et pratiques.
D'autres algorithmes de tri de nombres entiers avec des limites de temps plus faibles dans le pire des cas ne sont pas considérés comme pratiques pour les architectures informatiques à 64 bits ou moins.
Beaucoup de ces algorithmes sont connus, les performances dépendant du nombre d'éléments à trier, du nombre de bits par clé et du nombre de bits par mot de l'ordinateur exécutant l'algorithme de tri.
Considérations générales La complexité temporelle des algorithmes de tri d’entiers dépend généralement de trois paramètres : le nombre de valeurs à trier, la magnitude de la clé la plus grande possible à trier et le nombre de bits pouvant être représentés dans un seul mot machine de l'ordinateur sur lequel l'algorithme doit être exécuté. Typiquement, on suppose que ; c'est-à-dire que les mots machine sont suffisamment grands pour représenter un index dans la séquence de données d'entrée, et également suffisamment grands pour représenter une clé uniqueFredman & Willard (1993) .
Les algorithmes de tri de nombres entiers sont généralement conçus pour fonctionner soit dans la machine à pointeur, soit dans la machine RAM. La principale différence entre ces deux modèles réside dans la manière dont la mémoire peut être adressée. La machine RAM permet à toute valeur stockée dans un registre d'être utilisée comme adresse des opérations de lecture et d'écriture en mémoire, avec un coût unitaire par opération. Cette capacité permet à certaines opérations complexes sur les données d'être rapidement mises en œuvre à l'aide de recherches dans les tables. En revanche, dans le modèle de pointeur, les opérations de lecture et d'écriture utilisent les adresses stockées dans les pointeurs et il est interdit d'effectuer des opérations arithmétiques sur ces pointeurs. Dans les deux modèles, des valeurs de données peuvent être ajoutées et des opérations booléennes au niveau du bit et des opérations de décalage binaire peuvent généralement également être effectuées sur ces unités, en unités de temps par opération. Différents algorithmes de tri de nombres entiers supposent différentes hypothèses, toutefois, quant à savoir si la multiplication de nombres entiers est également autorisée en tant qu'opération temporelleLa question de savoir si une multiplication d'entiers ou si consulter un tableau sont permis revient à Fredman & Willard (1993) ; voir également Andersson, Miltersen & Thorup (1999).. D'autres modèles de calcul plus spécialisés, tels que la PRAM, ont également été envisagésReif (1985) ; commentaire dans Cole & Vishkin (1986) ; Hagerup (1987) ; Bhatt et al. (1991) ; Albers & Hagerup (1997)..
Andersson, Miltersen & Thorup (1999) ont montré que, dans certains cas, les multiplications ou les recherches dans les tables requises par certains algorithmes de tri d'entiers pourraient être remplacées par des opérations personnalisées qui seraient plus facilement implémentées dans le matériel, mais qui ne sont généralement pas disponibles sur des ordinateurs polyvalents. Thorup (2003) amélioré ceci en montrant comment remplacer ces opérations spéciales par les instructions de manipulation de champs de bits déjà disponibles sur les processeurs Pentium.
Tri par rapport aux files de priorité d'entiers Une file de priorité est une structure de données permettant de gérer un ensemble d'éléments munis de priorités numériques, comportant des opérations permettant de rechercher et de supprimer l'élément ayant la valeur de priorité minimale. Les files de priorité basées sur la comparaison, telles que le tas binaire, prennent un temps logarithmique par mise à jour, mais d'autres structures telles que l'arbre de van Emde Boas ou la file d'attente de compartiment peuvent être plus rapides pour les entrées dont les priorités sont de petits entiers. Ces structures de données peuvent être utilisées dans l'algorithme de tri par sélection, qui trie une collection d'éléments en recherchant et en supprimant de manière répétée le plus petit élément de la collection et en renvoyant les éléments dans l'ordre dans lequel ils ont été trouvés. Une file de priorité peut être utilisée pour gérer la collection d'éléments dans cet algorithme, et le temps pour cet algorithme sur une collection de éléments peut être limité par le temps nécessaire pour initialiser la file de priorité, puis pour effectuer opérations de recherche et suppression. Par exemple, l'utilisation d'un tas binaire comme file de priorité dans le tri par sélection conduit à l'algorithme de tri par tas, un algorithme de tri de comparaison de complexité temporelle en . Au lieu de cela, l'utilisation du tri par sélection avec une file d’attente donne une forme de tri par casier et l’utilisation d’arbres de Van Emde Boas ou d’autres files d’attente avec priorité entière conduit à d’autres algorithmes de tri d’entiers rapides.
Au lieu d'utiliser une file de priorité d'entiers dans un algorithme de tri, il est possible d'aller dans la direction opposée et d'utiliser les tris d'entiers comme sous-routine dans une structure de données de file de priorité d'entiers. Thorup (2007) a utilisé cette idée pour montrer que, s'il est possible de réaliser le tri d'entiers en temps linéaire par clé alors cette même complexité s'applique aux opérations d'insertion et de suppression dans une file de priorité. La réduction de Thorup est complexe et s’appuie cependant sur l'existence d'une multiplication rapide ou d'une recherche rapide dans une table mais il donne une file de priorité alternative utilisant l'addition et les opérations sur les booléens en temps par opération, multipliant au plus le temps par un logarithme itéré.
Utilisabilité Les algorithmes classiques de tri des nombres entiers de type tri pigeonhole, tri comptage et tri par base sont largement utilisés et pratiques. La plupart des recherches ultérieures sur les algorithmes de tri de nombres entiers ont été moins axées sur l'aspect pratique que sur les améliorations théoriques apportées à leur analyse des pires cas, et les algorithmes issus de cette ligne de recherche ne sont apparemment pas pratiques pour les architectures informatiques 64 bits actuelles, bien que des expériences ont montré que certaines de ces méthodes peuvent constituer une amélioration du tri de base pour les données de 128 bits ou plus par cléMcIlroy, Bostic & McIlroy (1993) ; Andersson & Nilsson (1998).. De plus, pour les grands ensembles de données, le modèle d'accès mémoire quasi aléatoire de nombreux algorithmes de tri d'entiers peuvent les handicaper par rapport aux algorithmes de tri de comparaison conçus pour la hiérarchie de mémoireRahman & Raman (1998). .
Le tri de nombres entiers constitue l'un des six tests de performances en mathématiques discrètes de systèmes de calcul à haute productivité DARPA DARPA HPCS Discrete Mathematics Benchmarks, Duncan A. Buell, Université de Caroline du Sud, 2011. et l'un des onze points de repère de la suite de tests de performances NAS .
Algorithmes pratiques Le tri pigeonhole et le tri comptage peuvent tous les deux trier éléments de données dont les clés sont comprises entre et dans le temps . Dans le tri pigeonhole, les pointeurs vers les éléments de données sont distribués dans une table de compartiments, représentés comme des types de données de collection tels que des listes chaînées, en utilisant les clés comme indices dans la table. Ensuite, tous les compartiments sont concaténés ensemble pour former la liste de sortieGoodrich & Tamassia (2002). Même si Cormen et al. (2001) a aussi établi une version de cet algorithme, la version qu'ils décrivent est adaptée aux entrées dont les clés sont des nombres réels plutôt que seulement des entiers. . Le tri comptage utilise une table de compteurs à la place d'une table de compartiments, pour déterminer le nombre d'articles avec chaque clé. Ensuite, un calcul de somme de préfixes est utilisé pour déterminer la plage de positions dans la sortie triée à laquelle les valeurs de chaque clé doivent être placées. Enfin, lors d'un deuxième passage sur l'entrée, chaque élément est déplacé à la position de sa clé dans le tableau de sortieCormen et al., 8.2 Counting Sort, 2001, .. Les deux algorithmes n'impliquent que de simples boucles sur les données d'entrée (prenant le temps ) et sur l'ensemble des clés possibles (prenant le temps ), donnant leur complexité temporelle en .
Le tri par base est un algorithme de tri qui fonctionne pour des clés plus grandes que le tri pigeonhole ou le tri comptage en effectuant plusieurs parcours des données. Chaque parcours trie l'entrée en utilisant uniquement une partie des clés, en utilisant un algorithme de tri différent (tel que le tri pigeonhole ou le tri de comptage) qui ne convient qu'aux petites clés. Pour diviser les clés en parties, l'algorithme de tri par base calcule la notation positionnelle pour chaque clé, en fonction de certaines bases choisies; ensuite, la partie de la clé utilisée pour la ème passe de l'algorithme est le ème chiffre dans la notation positionnelle pour la clé complète, en partant du chiffre le moins significatif et en progressant vers le plus significatif. Pour que cet algorithme fonctionne correctement, l'algorithme de tri utilisé à chaque parcours des données doit être stable : les éléments avec des chiffres égaux ne doivent pas changer de position les uns avec les autres. Pour une plus grande efficacité, la base doit être choisie pour être proche du nombre d'éléments de données, . De plus, l'utilisation d'une puissance de deux près de comme base permet de calculer rapidement les clés de chaque parcours en utilisant uniquement des opérations rapides de décalage binaire et de masque. Avec ces choix, et avec le tri pigeonhole ou le tri par comptage comme algorithme de base, l'algorithme de tri par base peut trier éléments de données ayant des clés dans la plage de à dans le temps Comrie (1929–1930) ; Cormen et al., 8.3 Radix Sort, 2001, ..
Algorithmes théoriques De nombreux algorithmes de tri d'entiers ont été développés dont l'analyse théorique montre qu'ils se comportent mieux que le tri par comparaison, le tri pigeonhole ou le tri par base pour des combinaisons suffisamment grandes de paramètres définissant le nombre d'éléments à trier, la plage de clés et la taille du mot machine. La performance d'un algorithme dépend des valeurs de ces paramètres. Cependant, malgré leurs avantages théoriques, ces algorithmes ne sont pas une amélioration pour les plages typiques de ces paramètres qui se posent dans des problèmes de tri pratiques.
Algorithmes pour les petites clés Un arbre de Van Emde Boas peut être utilisé comme file de priorité pour trier un ensemble de clés, chacune dans la plage de à , dans le temps . Il s'agit d'une amélioration théorique par rapport au tri par base lorsque est suffisamment grand. Cependant, pour utiliser un arbre de Van Emde Boas, il faut soit une mémoire directement accessible de mots, soit il faut la simuler à l'aide d'une table de hachage, en réduisant l'espace à une structure linéaire mais en rendant l'algorithme aléatoire.