Abstrait

AMÉLIORATION DES PERFORMANCES DU TRI DE SIGNATURE ALÉATOIRE À L'AIDE D'OPÉRATEURS DE HACHAGE ET DE BITWISE

Tamana Pathak et Dr Deepak Garg

Les recherches effectuées dans le domaine du tri d'entiers ont considérablement amélioré la borne inférieure et atteint le tri par comparaison, c'est-à-dire [1] pour un algorithme déterministe ou pour un algorithme de tri par base dans l'espace qui ne dépend que du nombre d'entiers d'entrée. Andersson et al. [2] ont présenté le tri par signature dans le temps et l'espace linéaires attendus, ce qui donne de très mauvaises performances que le tri rapide traditionnel. Il est bien connu que les entiers dans la plage [1, c] peuvent être triés dans le temps en utilisant le tri par base. Les entiers dans n'importe quelle plage [1, ] peuvent être triés dans le temps [1]. Cependant, ces algorithmes utilisent des mots de mémoire supplémentaire. Nous présentons une variante simple et stable du tri par signature pour le tri d'entiers, qui fonctionne dans le temps et utilise uniquement des mots de mémoire supplémentaire. Dans ce cadre, nous essayons d'améliorer les performances du tri par signature en implémentant différemment et en comparant ses performances par rapport aux algorithmes de tri traditionnels et en voyant l'effet de la taille du registre sur l'algorithme.