Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Tri de nombres entiers
Résumé
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 texte. 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 pigeonhole, 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.
La complexité temporelle des algorithmes de tri d’entiers dépend généralement de trois paramètres : le nombre n de valeurs à trier, la magnitude K de la clé la plus grande possible à trier et le nombre w 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é unique.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.