{"partition": "head_middle", "source_domain": "www.ilemaths.net", "digest": "sha1:OX2KILNXDKHVUVMHIEIN2PBM6HX6GNF4", "path": "/lustre/fsn1/projects/rech/qgz/uzq54wg/processed_redpajama/base_processing/output/fr/2014-15/000_00011.parquet"}
Algorithme de tri
Recherche : Encyclopédie
Les définitions
Top définitions
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z toutes les définitions
Algorithme de tri : encyclopédie mathématiques
Cet article est issu de l'encyclopédie libre Wikipedia.Vous pouvez consulter l'article ici ainsi que son historique.Les textes et les images sont disponibles sous les termes de la Licence de documentation libre GNU.
Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon un ordre déterminé. Les objets à trier font donc partie d'un ensemble muni d'une relation d'ordre (de manière générale un ordre total). Les ordres les plus utilisés sont l’ordre numérique et l'ordre lexicographique (dictionnaire).
Suivant la relation d'ordre considérée, une même collection d’objets peut donner lieu à divers arrangements, pourtant il est possible de définir un algorithme de tri indépendamment de la fonction d’ordre utilisée. Celui-ci ne fera qu'utiliser une certaine fonction d’ordre correspondant à une relation d’ordre qui doit permettre de comparer tout couple d'éléments de la collection.
1.1 Complexité algorithmique
1.2 Caractère en place
1.3 Caractère stable
1.4 Tri interne et externe
1.5 Tri parallèle
2 Exemples d'algorithmes de tri
2.1 Tris par comparaison
2.1.1 Algorithmes lents
2.1.2 Algorithmes plus rapides
2.1.3 Comparaison des algorithmes de tris en place
22.214.171.124 Comparaisons tris sur grands tableaux
2.2 Tris utilisant la structure des données
2.3 Tris volumineux
2.3.1 Tris bande
3 Liens externes
4 Notes et références
Classification[modifier | modifier le code]
La classification des algorithmes de tri est très importante, car elle permet de choisir l’algorithme le plus adapté au problème traité, tout en tenant compte des contraintes imposées par celui-ci.
On distingue, tout d'abord, les algorithmes de tri d'application générale, procédant par comparaisons entre des paires d'éléments, et les algorithmes plus spécialisés faisant des hypothèses restrictives sur la structure des données entrées (par exemple, le tri par comptage, applicable uniquement si les données sont prises parmi un petit ensemble connu à l'avance). Si l'on ne précise rien, on entend habituellement par « algorithme de tri » un algorithme général de tri par comparaison.
Les principales caractéristiques qui permettent de différencier les algorithmes de tri sont : la complexité algorithmique, les ressources nécessaires (notamment en termes d'espace mémoire utilisé) et le caractère stable.
Complexité algorithmique[modifier | modifier le code]
La complexité algorithmique temporelle dans le pire des cas permet de fixer une borne supérieure du nombre d'opérations qui seront nécessaires pour trier un ensemble de n éléments.
La complexité algorithmique temporelle en moyenne : c’est le nombre d'opérations élémentaires effectuées en moyenne pour trier une collection d’éléments. Elle permet de comparer les algorithmes de tris et don