Tri de nombres 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 n éléments peut être limité par le temps nécessaire pour initialiser la file de priorité, puis pour effectuer n 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 O(n log n) . 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. [5]

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 T(n) + T(log n) + T(log log n) + ... par opération, multipliant au plus le temps par un logarithme itéré.[5]

Les algorithmes classiques de tri des nombres entiers de type tri pigeonhole, tri comptage et tri par base sont largement utilisés et pratiques[6]. 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é[6]. 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émoire[7].

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 [8] et l’un des onze points de repère de la suite de tests de performances NAS .

Un arbre de Van Emde Boas peut être utilisé comme file de priorité pour trier un ensemble de n clés, chacune dans la plage de 0 à K − 1, dans le temps O(n log log K) . Il s'agit d'une amélioration théorique par rapport au tri par base lorsque K est suffisamment grand. Cependant, pour utiliser un arbre de Van Emde Boas, il faut soit une mémoire directement accessible de K 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.

Kirkpatrick & Reisch (1984) ont développé une technique plus sophistiquée, assez similaire et avec de meilleures performances théoriques. Ils ont observé que chaque lecture des données dans le tri par base peut être interprétée comme une technique de réduction de plage qui, en temps linéaire, réduit la taille de clé maximale d'un facteur de n ; au lieu de cela, leur technique réduit la taille de la clé à la racine carrée de sa valeur précédente (divisant par deux le nombre de bits nécessaires pour représenter une clé), toujours en temps linéaire. Comme dans le tri par base, ils interprètent les clés comme des nombres en base b de 2 chiffres pour une valeur de b qui est approximativement √K Ils regroupent ensuite les éléments à trier en compartiments en fonction de leurs chiffres élevés, en temps linéaire, à l'aide d'une grande mémoire directement accessible mais non initialisée ou d'une table de hachage. Chaque compartiment a un représentant, l'article dans le compartiment avec la plus grande clé; ils trient ensuite la liste des éléments en utilisant comme clés les chiffres hauts pour les représentants et les chiffres bas pour les non-représentants. En regroupant à nouveau les éléments de cette liste dans des compartiments, chaque compartiment peut être placé dans un ordre trié, et en extrayant les représentants de la liste triée, les compartiments peuvent être concaténés ensemble dans un ordre trié. Ainsi, en temps linéaire, le problème de tri est réduit à un autre problème de tri récursif dans lequel les clés sont beaucoup plus petites, la racine carrée de leur amplitude précédente. La répétition de cette réduction de plage jusqu'à ce que les clés soient suffisamment petites pour trier le compartiment conduit à un algorithme avec le temps d'exécution O(n log log_n K) .

Un algorithme aléatoire compliqué de Han & Thorup (2002) dans le modèle de calcul "RAM de mots" permet de réduire encore plus ces limites de temps, à O(n√log log K) .

Un algorithme de tri d'entiers est dit non conservateur s'il nécessite une taille de mot w qui est significativement plus grande que log max(n, K)[12] . Un exemple extrême, si w ≥ K, et que toutes les clés sont distinctes, alors l'ensemble des clés peut être trié en temps linéaire en le représentant comme un tableau de bits, avec un bit à la position i lorsque i est l'une des clés d'entrée, puis en supprimant à plusieurs reprises le bit le moins significatif. [13]

L'algorithme de tri condensé non conservateur d' Albers & Hagerup (1997) utilise un sous-programme, basé sur le tri bitonique de Ken Batcher, pour fusionner deux séquences de clés triées suffisamment courtes pour être regroupées dans un seul mot machine. L'entrée de l'algorithme de tri condensés, une séquence d'articles stockés un par mot, est transformée en une forme condensés, une séquence de mots contenant chacun plusieurs éléments dans un ordre trié ; en utilisant ce sous-programme à plusieurs reprises pour doubler le nombre d'éléments condensés dans chacun mot. Une fois la séquence sous forme compactée, Albers et Hagerup utilisent une forme de tri fusion pour la trier. Lorsque deux séquences sont fusionnées pour former une seule séquence plus longue, le même sous-programme de tri bitonique peut être utilisé pour extraire à plusieurs reprises des mots condensés constitués des plus petits éléments restants des deux séquences. Cet algorithme gagne suffisamment d'accélération de sa représentation condensée pour trier son entrée en temps linéaire chaque fois qu'il est possible qu'un seul mot contienne des clés Ω(log n log log n) ; c'est-à-dire, lorsque log K log n log log n ≤ cw pour une constante c > 0 .

Le tri pigeonhole, le tri par comptage, le tri par base et le tri par arbre Van Emde Boas fonctionnent tous mieux lorsque la taille de la clé est petite; pour les clés suffisamment grandes, elles deviennent plus lentes que les algorithmes de tri comparatif. Cependant, lorsque la taille de la clé ou la taille du mot est très grande par rapport au nombre d'éléments (ou de manière équivalente lorsque le nombre d'éléments est petit), il peut de nouveau devenir possible de trier rapidement, en utilisant différents algorithmes qui tirent parti du parallélisme inhérent dans la capacité d'effectuer des opérations arithmétiques sur de gros mots.

Un premier résultat dans cette direction a été fourni par Ajtai, Fredman & Komlós (1984) en utilisant le modèle de calcul à sonde cellulaire (un modèle artificiel dans lequel la complexité d'un algorithme n'est mesurée que par le nombre d'accès à la mémoire qu'il effectue). S'appuyant sur leurs travaux, Fredman & Willard (1994) ont décrit deux structures de données, le tas Q et le tas atomique, qui peuvent être implémentées sur une machine à accès aléatoire. Le segment Q est une version bit parallèle d'un tri binaire, et permet à la fois des opérations de file de priorité et des requêtes de successeur et prédécesseur à effectuer en temps constant pour des ensembles d'éléments de taille O((log N)^1/4), où N ≤ 2^w est la taille des tables précalculées nécessaires pour implémenter la structure de données. Le tas atomique est un B-arbre dans lequel chaque nœud d'arbre est représenté comme un tas Q; il permet des opérations de file de priorité en temps constant (et donc un tri) pour des ensembles d'éléments de taille (log N)^O(1) .

Andersson et al. (1998) fournissent un algorithme aléatoire appelé tri par signature qui permet un tri linéaire dans le temps d'ensembles jusqu'à 2^{O((log w)1/2 − ε)} éléments à la fois, pour toute constante ε > 0 . Comme dans l'algorithme de Kirkpatrick et Reisch, ils effectuent une réduction de plage en utilisant une représentation des clés sous forme de nombres dans la base b pour un choix judicieux de b . Leur algorithme de réduction de plage remplace chaque chiffre par une signature, qui est une valeur hachée avec O(log n) bits de sorte que différentes valeurs de chiffre ont des signatures différentes. Si n est suffisamment petit, les nombres formés par ce processus de remplacement seront significativement plus petits que les clés d'origine, permettant à l'algorithme de tri condensé non conservateur d' Albers & Hagerup (1997) de trier les nombres remplacés en temps linéaire. À partir de la liste triée des nombres remplacés, il est possible de former un tri condensé des clés en temps linéaire, et les enfants de chaque nœud du tri peuvent être triés récursivement en utilisant uniquement des clés de taille b, après quoi un parcours d'arbre produit l'ordre trié des articles.

Fredman & Willard (1993) ont présenté le modèle d'analyse transdichotomique pour les algorithmes de tri d'entiers, dans lequel rien n'est supposé sur la plage des clés entières et il faut limiter les performances de l'algorithme en fonction du nombre de valeurs de données uniquement. Alternativement, dans ce modèle, le temps d'exécution d'un algorithme sur un ensemble de n éléments est supposé être le temps d'exécution du pire cas pour toute combinaison possible de valeurs de K et   w . Le premier algorithme de ce type était l'algorithme de tri des arbres de fusion de Fredman et Willard, qui s'exécute dans le temps O(n log n / log log n) ; il s'agit d'une amélioration par rapport au tri par comparaison pour tout choix de K et   w . Une version alternative de leur algorithme qui inclut l'utilisation de nombres aléatoires et d'opérations de division entière améliore cela à O(n√log n) .

Depuis leur travail, des algorithmes encore meilleurs ont été développés. Par exemple, en appliquant à plusieurs reprises la technique de réduction de la plage Kirkpatrick - Reisch jusqu'à ce que les clés soient suffisamment petites pour appliquer l'algorithme de tri condensé Albers – Hagerup, il est possible de trier dans le temps O(n log log n) ; cependant, la partie réduction de plage de cet algorithme nécessite soit une grande mémoire (proportionnelle à √K ), soit une randomisation sous forme de tables de hachage[14].

Han & Thorup (2002) ont montré comment trier en temps aléatoire O(n√log log n) . Leur technique consiste à utiliser des idées liées au tri des signatures pour partitionner les données en de nombreuses petites sous-listes, d'une taille suffisamment petite pour que le tri des signatures puisse trier chacune d'elles efficacement. Il est également possible d'utiliser des idées similaires pour trier les entiers de manière déterministe dans le temps O(n log log n) et en mémoire linéaire[15]. En utilisant uniquement des opérations arithmétiques simples (pas de multiplications ou de recherches de table), il est possible de trier dans le temps aléatoire attendu O(n log log n) [16] ou de manière déterministe dans le temps O(n (log log n)^{1 + ε}) pour toute constante ε > 0 .