| Property |
Value |
| dbo:abstract
|
- Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle « est inférieur ou égal à ». Les algorithmes de tri sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche dichotomique. Ils peuvent également servir pour mettre des données sous forme canonique ou les rendre plus lisibles pour l'utilisateur. La collection à trier est souvent donnée sous forme de tableau, afin de permettre l'accès direct aux différents éléments de la collection, ou sous forme de liste, ce qui peut se révéler être plus adapté à certains algorithmes et à l'usage de la programmation fonctionnelle. Bon nombre d'algorithmes de tri procèdent par comparaisons successives, et peuvent donc être définis indépendamment de l'ensemble auquel appartiennent les éléments et de la relation d’ordre associée. Un même algorithme peut par exemple être utilisé pour trier des réels selon la relation d'ordre usuelle « est inférieur ou égal à » et des chaînes de caractères selon l'ordre lexicographique. Ces algorithmes se prêtent naturellement à une implémentation polymorphe. Les algorithmes de tri sont souvent étudiés dans les cours d'algorithmique pour introduire des notions comme la complexité algorithmique ou la terminaison. (fr)
- Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle « est inférieur ou égal à ». Les algorithmes de tri sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche dichotomique. Ils peuvent également servir pour mettre des données sous forme canonique ou les rendre plus lisibles pour l'utilisateur. La collection à trier est souvent donnée sous forme de tableau, afin de permettre l'accès direct aux différents éléments de la collection, ou sous forme de liste, ce qui peut se révéler être plus adapté à certains algorithmes et à l'usage de la programmation fonctionnelle. Bon nombre d'algorithmes de tri procèdent par comparaisons successives, et peuvent donc être définis indépendamment de l'ensemble auquel appartiennent les éléments et de la relation d’ordre associée. Un même algorithme peut par exemple être utilisé pour trier des réels selon la relation d'ordre usuelle « est inférieur ou égal à » et des chaînes de caractères selon l'ordre lexicographique. Ces algorithmes se prêtent naturellement à une implémentation polymorphe. Les algorithmes de tri sont souvent étudiés dans les cours d'algorithmique pour introduire des notions comme la complexité algorithmique ou la terminaison. (fr)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 36259 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
| |
| prop-fr:bnf
| |
| prop-fr:contenu
|
- Le problème du tri consiste, étant donné une suite d’éléments d’un ensemble totalement ordonné , à déterminer une permutation de telle que soit triée.
On suppose pour simplifier que tous les éléments à trier sont distincts, ce qui rend la permutation unique. Le résultat reste vrai a fortiori dans le cas général.
Un algorithme de tri par comparaisons successives se modélise comme un arbre binaire. Chaque nœud de l'arbre correspondant à une comparaison entre deux éléments et , et comportant deux fils représentant les deux comparaisons suivantes possibles selon l'issue de la première.
À chaque exécution de l'algorithme sur une permutation de peut être associé le chemin allant de la racine à une feuille correspondant à cette exécution ; deux entrées différentes sont nécessairement associées à deux chemins différents. Le nombre de permutations de éléments distincts deux à deux étant , le nombre de feuilles de l'arbre est supérieur ou égal à cette valeur.
Borne inférieure pour la complexité dans le pire cas
Notons la hauteur de l'arbre . Le nombre maximal de feuilles dans un arbre binaire de hauteur est .
Il vient donc : . D'une part, . D'autre part, en utilisant la formule de Stirling, on obtient asymptotiquement .
Le fait qu'il existe des tris en montre d'autre part qu'il est possible d'avoir asymptotiquement . Cette borne donne donc bien la complexité minimum dans le pire cas d'un algorithme de tri par comparaisons.
Borne inférieure pour la complexité en moyenne
Étant donné un arbre binaire , on note la profondeur moyenne des feuilles de . Si toutes les permutations des éléments en entrée sont équiprobables, alors le nombre moyen de comparaisons du tri avec un arbre de comparaisons est .
Pour un nombre de nœuds fixé, les arbres minimisant sont les arbres binaires complets . En effet, dans un arbre non complet, il existe une feuille de profondeur et une feuille de profondeur au plus . En raccrochant la première feuille à la seconde, on obtient un arbre tel que .
La fonction prend la même valeur pour tous les arbres binaires complets à feuilles. Soit l'un d'entre eux et sa hauteur. Toutes les feuilles sont de profondeur au moins , donc la profondeur moyenne des feuilles est au moins . (fr)
- Le problème du tri consiste, étant donné une suite d’éléments d’un ensemble totalement ordonné , à déterminer une permutation de telle que soit triée.
On suppose pour simplifier que tous les éléments à trier sont distincts, ce qui rend la permutation unique. Le résultat reste vrai a fortiori dans le cas général.
Un algorithme de tri par comparaisons successives se modélise comme un arbre binaire. Chaque nœud de l'arbre correspondant à une comparaison entre deux éléments et , et comportant deux fils représentant les deux comparaisons suivantes possibles selon l'issue de la première.
À chaque exécution de l'algorithme sur une permutation de peut être associé le chemin allant de la racine à une feuille correspondant à cette exécution ; deux entrées différentes sont nécessairement associées à deux chemins différents. Le nombre de permutations de éléments distincts deux à deux étant , le nombre de feuilles de l'arbre est supérieur ou égal à cette valeur.
Borne inférieure pour la complexité dans le pire cas
Notons la hauteur de l'arbre . Le nombre maximal de feuilles dans un arbre binaire de hauteur est .
Il vient donc : . D'une part, . D'autre part, en utilisant la formule de Stirling, on obtient asymptotiquement .
Le fait qu'il existe des tris en montre d'autre part qu'il est possible d'avoir asymptotiquement . Cette borne donne donc bien la complexité minimum dans le pire cas d'un algorithme de tri par comparaisons.
Borne inférieure pour la complexité en moyenne
Étant donné un arbre binaire , on note la profondeur moyenne des feuilles de . Si toutes les permutations des éléments en entrée sont équiprobables, alors le nombre moyen de comparaisons du tri avec un arbre de comparaisons est .
Pour un nombre de nœuds fixé, les arbres minimisant sont les arbres binaires complets . En effet, dans un arbre non complet, il existe une feuille de profondeur et une feuille de profondeur au plus . En raccrochant la première feuille à la seconde, on obtient un arbre tel que .
La fonction prend la même valeur pour tous les arbres binaires complets à feuilles. Soit l'un d'entre eux et sa hauteur. Toutes les feuilles sont de profondeur au moins , donc la profondeur moyenne des feuilles est au moins . (fr)
|
| prop-fr:description
|
- Visualisation de différents tris à l’aide de couleurs (fr)
- Visualisation de différents tris à l’aide de couleurs (fr)
|
| prop-fr:déroulante
| |
| prop-fr:fr
|
- tri partiel (fr)
- tri partiel (fr)
|
| prop-fr:isbn
|
- 2 (xsd:integer)
- 978 (xsd:integer)
|
| prop-fr:langue
|
- en (fr)
- fr (fr)
- en (fr)
- fr (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:nom
|
- Soria (fr)
- Froidevaux (fr)
- Gaudel (fr)
- Soria (fr)
- Froidevaux (fr)
- Gaudel (fr)
|
| prop-fr:numéroChapitre
| |
| prop-fr:pagesTotales
| |
| prop-fr:prénom
|
- Marie-Claude (fr)
- Christine (fr)
- Michèle (fr)
- Marie-Claude (fr)
- Christine (fr)
- Michèle (fr)
|
| prop-fr:titre
|
- Types de données et algorithmes (fr)
- Types de données et algorithmes (fr)
|
| prop-fr:trad
|
- Partial sorting (fr)
- Partial sorting (fr)
|
| prop-fr:url
|
- https://imgur.com/gallery/voutF|titre=Sorting Algorithms Visualized (fr)
- https://imgur.com/gallery/voutF|titre=Sorting Algorithms Visualized (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- McGraw-Hill (fr)
- McGraw-Hill (fr)
|
| dct:subject
| |
| rdfs:comment
|
- Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle « est inférieur ou égal à ». Les algorithmes de tri sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche dichotomique. Ils peuvent également servir pour mettre des données sous forme canonique ou les rendre plus lisibles pour l'utilisateur. (fr)
- Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle « est inférieur ou égal à ». Les algorithmes de tri sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche dichotomique. Ils peuvent également servir pour mettre des données sous forme canonique ou les rendre plus lisibles pour l'utilisateur. (fr)
|
| rdfs:label
|
- Algorithme de tri (fr)
- Ordenatze algoritmo (eu)
- Sorting algorithm (en)
- Thuật toán sắp xếp (vi)
- Алгоритм сортировки (ru)
- Алгоритм сортування (uk)
- ソート (ja)
|
| rdfs:seeAlso
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:mainArticleForCategory
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
