Voir la source de Tri par tas

Vous n’avez pas la permission de modifier cette page, pour la raison suivante :

Votre adresse IP fait partie d’une plage qui a été bloquée sur tous les wikis de la Fondation Wikimédia.

Le blocage a été effectué par ‪Hasley‬. Le motif invoqué est Open proxy/Webhost: See the help page if you are affected: .

Début du blocage : 18 décembre 2022 à 17:21
Expiration du blocage : 18 décembre 2025 à 17:21

Votre adresse IP actuelle est 62.210.136.28. La plage bloquée est 62.210.0.0/16.

Veuillez inclure tous les détails ci-dessus dans toutes les demandes que vous effectuerez. Si vous pensez avoir été bloqué(e) par erreur, vous pouvez trouver plus d’informations et d’instructions dans la politique globale Pas de serveurs mandataires ouverts.

Sinon, pour discuter du blocage, veuillez publier une demande de révision sur Méta-Wiki. Vous pouvez également envoyer un courriel à la file des coordinateurs VRT à stewards@wikimedia.org, en incluant tous les détails ci-dessus.

Vous pouvez voir et copier le contenu de cette page.

{{Infobox Algorithme}}
[[Fichier:Heap sort example.gif|thumb|300px|Animation montrant le fonctionnement du tri par tas (Heapsort).]]
En [[informatique]], le '''tri par tas''' (en [[anglais]] ''{{Lang|en|heapsort}}'') est un [[algorithme de tri]] par comparaisons. Cet algorithme est de [[complexité en temps|complexité]] asymptotiquement optimale<ref>C'est-à-dire que l'on démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure.</ref>. Sa complexité est proportionnelle à <math>n \log n </math> où <math>n</math> est la longueur du tableau à trier. Le tri par tas se fait ''en place'', c’est-à-dire qu’il ne nécessite pas l'allocation d'une zone mémoire supplémentaire (plus précisément il ne nécessite qu'une allocation d'une zone mémoire de taille <math>O(1)</math>){{Sfn|Cormen|Leiserson|Rivest|p=121|Stein|2004}}. Par contre, il n'est pas stable, c'est-à-dire que l'ordre original d'éléments auxquels est associée une même [[Clé (structure de données)|clé de tri]] n'est pas en général préservé.

Son inconvénient majeur est sa lenteur comparé au [[tri rapide]] (qui est [[Complexité en moyenne des algorithmes|en moyenne]] deux fois plus rapide) : sur un tableau de taille importante, il sera amené à traiter un nombre élevé d'emplacements mémoire dont l’éloignement peut dépasser la capacité du cache, ce qui ralentit l'accès à la mémoire et l’exécution de l’algorithme{{référence nécessaire}}.

== Historique ==
Le tri par tas a été trouvé par {{Lien|langue=en|trad=J. W. J. Williams|fr=J. W. J. Williams}} en 1964{{Sfn|J. W. J. Williams|1964}}. Il y introduit la structure de [[Tas (informatique)|tas]], qui servira dans d'autres algorithmes. La même année, [[Robert W. Floyd]] améliore l'algorithme pour que le tri puisse se faire en place{{Sfn|Robert W. Floyd|1964}}{{,}}<ref>{{Ouvrage|langue=en|auteur1=Peter Brass|titre=Advanced data structures|éditeur=Cambrige University Press|année=2008|pages totales=474|passage=208|isbn=978-0-521-88037-4|oclc=221147457|doi=10.1017/CBO9780511800191|accès doi=payant|consulté le=2024-05-29}}</ref>.

== Principe ==
C'est un [[tri par file de priorité]] utilisant le [[Tas (informatique)|tas]] comme file de priorité. Il tire particulièrement avantage de la suppression de clef en <math>\Theta(\log n)</math> et la création du tas à partir d'un tableau en <math>\Theta(n)</math><ref>{{Lien web |langue=fr |auteur=François Schwarzentruber |titre=File de priorité et tas binaire |url=https://people.irisa.fr/Francois.Schwarzentruber/algo1/02tas.pdf |format=pdf |accès url=libre |date=18 février 2021 |consulté le=16 octobre 2024}}</ref>.

Une implémentation possible de cet algorithme consiste à voir le tableau comme un [[arbre binaire]]. Le premier élément est la racine, le deuxième et le troisième sont les deux descendants du premier élément, etc. Ainsi le <math>n</math><sup>e</sup> élément a pour enfants les éléments <math>2n</math> et <math>2n+1</math> si l'indexation se fait à partir de 1 (<math>2n + 1</math> et <math>2n+2</math> si l'indexation se fait à partir de 0).
Si le tableau n'est pas de taille <math>(2^n - 1)</math>, les branches ne se finissent pas toutes à la même profondeur.

Dans l'algorithme, on cherche à obtenir un [[tas (informatique)|tas]], c'est-à-dire un [[arbre binaire]] vérifiant les propriétés suivantes (les deux premières propriétés découlent de la manière dont on considère les éléments du tableau){{Sfn|Cormen|Leiserson|Rivest|p=121-123|Stein|2004}} :
* la différence maximale de profondeur entre deux feuilles est de 1 (''i.e.'' toutes les feuilles se trouvent sur la dernière ou sur l'avant-dernière ligne) ;
* les feuilles de profondeur maximale sont « tassées » sur la gauche.
* chaque nœud est de valeur supérieure (resp. inférieure) à celles de ses deux fils, pour un tri ascendant (resp. descendant).
Il en découle que la racine du tas (le premier élément) contient la valeur maximale (resp. minimale) de l'arbre. Le tri est fondé sur cette propriété.

Comme expliqué plus haut, un tas ou un [[arbre binaire]] presque complet peut être stocké dans un tableau, en posant que les deux descendants de l'élément d'indice <math>n</math> sont les éléments d'indices <math>2n</math> et <math>2n+1</math> (pour un tableau indicé à partir de 1). En d'autres termes, les nœuds de l'arbre sont placés dans le tableau ligne par ligne, chaque ligne étant décrite de gauche à droite. Pour la suite, nous considérons que l'on trie par ordre croissant.

L'opération de base de ce tri est le ''tamisage'', ou ''percolation'', d'un élément, supposé le seul « mal placé » dans un arbre qui est presque un tas. Elle permet de pouvoir insérer un élément sans perdre la structure de tas. Cette procédure prend en argument un arbre <math>A</math> et un indice <math>i</math>. En supposant que les deux sous-arbres soient des tas et que <math>A[i]</math> soit plus petit que ses deux enfants, le rôle de l'opération de tamisage consiste à échanger <math>A[i]</math> avec le plus grand de ses fils, et ainsi de suite récursivement jusqu'à ce qu'il soit à sa place{{Sfn|Cormen|Leiserson|Rivest|p=124-125|Stein|2004}}.

Pour construire un tas à partir d'un arbre quelconque, on tamise les racines de chaque sous-tas, de bas en haut et de droite à gauche. On commence donc par les sous-arbres « élémentaires » — contenant deux ou trois nœuds, donc situés en bas de l'arbre. Pour un arbre représenté sous forme de tableau, cela revient juste à appliquer la procédure de tamisage de la fin du tableau jusqu'au premier élément<ref>On peut même commencer à {{Code|code=longueur[A]/2}}, car chaque nœud après est une feuille donc déjà un tas.</ref>{{,}}{{Sfn|Cormen|Leiserson|Rivest|p=126-128|Stein|2004}}.

La racine de ce tas <math>A[1]</math> est donc la valeur maximale du tableau, on l'échange avec <math>A[n]</math> où <math>n</math> est la longueur de <math>A</math>. On veut alors que <math>A[1 \cdots (n-1)]</math> reste un tas, pour ça il suffit de tamiser la nouvelle racine. En répétant l'opération sur le tas restreint jusqu'à l'avoir vidé on obtient par un tableau trié{{Sfn|Cormen|Leiserson|Rivest|p=129|Stein|2004}}.

== Pseudo-code ==
[[File:Principe tri par tas.svg|thumb|Application de l'algorithme.]]
On fait l'hypothèse que l'arbre est un tableau indexé entre <code>1</code> et <code>longueur</code>, <code>arbre[i]</code> désigne le i<sup>ème</sup> élément de ce tableau.

 
 
  '''fonction''' tamiser(arbre, nœud, n) :
    ''(* descend arbre[nœud] à sa place, sans dépasser l'indice n *)''
    k := nœud
    j := 2k
    '''tant que''' j ≤ n
       '''si''' j < n et arbre[j] < arbre[j+1]
          j := j+1
       '''fin si'''
       '''si''' arbre[k] < arbre[j]
          échanger arbre[k] et arbre[j]
          k := j
          j := 2k
       '''sinon'''
          j := n+1
       '''fin si'''
    '''fin tant que'''
 '''fin fonction'''
 
 '''fonction''' triParTas(arbre, longueur) :
    '''pour''' i := longueur/2 à 1
        tamiser(arbre, i, longueur)
    '''fin pour'''
    '''pour''' i := longueur à 2
        échanger arbre[i] et arbre[1]
        tamiser(arbre, 1, i-1)
    '''fin pour'''
 '''fin fonction'''

À la fin de la fonction <code>triParTas</code> le tableau <code>arbre</code> est trié suivant l'ordre croissant. Il suffit d'inverser les opérateurs de comparaison pour obtenir un tri dans l'ordre décroissant.

== Analyse ==
Cet algorithme permet de trier sur place les éléments d'un tableau en un temps de l'ordre de <math>n \log n </math>, où <math>n</math> est le nombre d'éléments à trier. La complexité entre le meilleur des cas et le pire des cas ne varie que d'un facteur constant<ref>[https://dx.doi.org/10.1006/jagm.1993.1031 The Analysis of Heapsort, Schaffer R. and Sedgewick R., 2002.]</ref>. L'étape la plus coûteuse de l'algorithme est la seconde boucle, c'est-à-dire l'extraction des éléments du tas. La première étape, consistant à construire le tas, est effectuée en temps linéaire en ''n''.

Les principaux atouts de cette méthode sont la faible consommation mémoire et l'efficacité, optimale étant donné qu'on ne fait aucune hypothèse sur la nature des données à trier.

== Variantes et améliorations ==
{{Section vide ou incomplète|à faire=traduire la section de l'article en anglais}}
* Quand le tableau est déjà trié, le tri par tas le mélange d'abord avant de le retrier. L'algorithme [[Smoothsort]]<ref>{{Ouvrage|langue=en|auteur1=Edsger W. Dijkstra|titre=Smoothsort, an alternative for sorting in situ|éditeur=Center for American History, [[Université du Texas à Austin]]|série=E. W. Dijkstra Archive|numéro dans collection=796-a|pages totales=16|lire en ligne=https://www.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/EWD796a.html|accès url=libre|consulté le=2024-05-29}}</ref> a pour but de pallier cet inconvénient. Comme le tri par tas, la complexité dans le pire des cas est en <math>O(n \log n)</math> mais en <math>O(n)</math> si la liste est presque trié. {{Référence nécessaire|Cependant la complexité moyenne reste en <math>O(n \log n)</math>, et en raison de sa complexité il est rarement utilisé|date=29 mai 2024}}.
* À la fin du tri par tas, pour les 15 derniers éléments environ, {{Référence nécessaire|l'algorithme effectue plusieurs fois de suite les mêmes inversions, ce qui est inutile|date=29 mai 2024}}. On peut à la place arrêter l'algorithme quand il n'y a plus beaucoup d'éléments et passer à un autre. Les données qui restent sont à peu près triées à l'envers. On peut donc, par exemple, retourner les données restantes (avec une inversion du {{1er}} et du dernier, du {{2e}} et de l'avant-dernier etc.) puis effectuer un [[tri par insertion]].

== Liens externes ==
* {{en}} [https://www.toptal.com/developers/sorting-algorithms Illustration dynamique du tri par tas ]

== Notes et références ==
{{Traduction/Référence|lang1=en|art1=Heapsort|id1=1220986714}}
{{Autres projets
 | wikibooks         = Implémentation d'algorithmes classiques/Algorithmes de tri/Tri par tas
 | wikibooks titre   = Implémentations du tri par tas
}}
{{Références}}

== Bibliographie ==
{{Légende plume}}

* {{Article|langue=en|auteur1=J. W. J. Williams|titre=Algorithm 232 – Heapsort|périodique=[[Communications of the ACM]]|volume=7|numéro=6|date=1964-06-01|doi=10.1145/512274.512284|accès doi=libre}}
* {{Article|langue=en|auteur1=Robert W. Floyd|titre=Algorithm 245 – Treesort 3|périodique=[[Communications of the ACM]]|volume=7|numéro=12|date=1964-12-01|doi=10.1145/355588.365103|s2cid=52864987|accès doi=libre|accès url=libre}}
* {{Ouvrage|langue=en|auteur1=Donald Ervin Knuth|titre=The Art of Computer Programming|volume=3|titre volume=Sorting and searching|éditeur=Addison-Wesley|année=1998|mois=01|numéro édition=2|pages totales=780|isbn=978-0-201-89685-5|numéro chapitre=5.2.3|titre chapitre=Sorting by Selection}}
* {{Ouvrage|auteur1=Thomas Cormen|auteur2=Charles Leiserson|auteur3=Ronald Rivest|auteur4=Clifford Stein|traducteur=Georges-Louis Kocher|titre=Introduction à l'algorithmique|titre original={{langue|en|Introduction to algorithms}}|lieu=Paris|éditeur=[[Éditions Dunod|Dunod]]|année=2004|numéro édition=2|année première édition=1990|pages totales=1146|isbn=2-10-003922-9|numéro chapitre=6|titre chapitre=Tri par tas|plume=oui}}
{{Palette|Algorithmes de tri}}
{{Portail|informatique théorique}}

[[Catégorie:Algorithme de tri|Tas]]

[[no:Sorteringsalgoritme#Heap sort]]

Modèles utilisés par cette page :

Modèle:, (voir la source) (protégé)
Modèle:1er (voir la source) (protégé)
Modèle:2e (voir la source) (protégé)
Modèle:Abréviation discrète (voir la source) (protégé)
Modèle:Article (voir la source) (protégé)
Modèle:Autres projets (voir la source) (protégé)
Modèle:Autres projets/styles.css (voir la source) (semi-protection étendue)
Modèle:Catégorisation badges (voir la source) (protégé)
Modèle:Classes début infobox (voir la source) (protégé)
Modèle:Code (modifier)
Modèle:En (voir la source) (protégé)
Modèle:Et al. (voir la source) (semi-protection étendue)
Modèle:Fix (voir la source) (semi-protection étendue)
Modèle:Indication de langue (voir la source) (protégé)
Modèle:Infobox/Pictogramme/informatique.css (voir la source) (semi-protection étendue)
Modèle:Infobox Algorithme (modifier)
Modèle:Infobox en Lua (voir la source) (semi-protection étendue)
Modèle:Lang (voir la source) (protégé)
Modèle:Langue (voir la source) (protégé)
Modèle:Lien (voir la source) (protégé)
Modèle:Lien web (voir la source) (protégé)
Modèle:Liste horizontale (voir la source) (semi-protection étendue)
Modèle:Légende plume (voir la source) (protégé)
Modèle:Méta bandeau de section (voir la source) (protégé)
Modèle:Méta lien vers portail (voir la source) (protégé)
Modèle:Méta lien vers portail/Catégorisation (voir la source) (protégé)
Modèle:Méta palette de navigation (voir la source) (protégé)
Modèle:Méta palette de navigation sous-groupe (voir la source) (protégé)
Modèle:Nom langue (voir la source) (protégé)
Modèle:Ordinal (voir la source) (protégé)
Modèle:Ouvrage (voir la source) (protégé)
Modèle:P. (voir la source) (protégé)
Modèle:Palette (voir la source) (protégé)
Modèle:Palette Algorithmes de tri (modifier)
Modèle:Plume (voir la source) (protégé)
Modèle:Portail (voir la source) (protégé)
Modèle:Portail informatique théorique (modifier)
Modèle:Référence Harvard sans parenthèses (voir la source) (protégé)
Modèle:Référence nécessaire (voir la source) (protégé)
Modèle:Références (voir la source) (protégé)
Modèle:Section vide ou incomplète (voir la source) (protégé)
Modèle:Sfn (voir la source) (semi-protection étendue)
Modèle:Suivi des biographies (voir la source) (protégé)
Modèle:Tnavbar (voir la source) (protégé)
Modèle:Traduction/Référence (voir la source) (protégé)
Modèle:Traduction/Référence/Lien (voir la source) (protégé)
Modèle:Trim (voir la source) (protégé)
Module:Bandeau (voir la source) (protégé)
Module:Bandeau/Class (voir la source) (protégé)
Module:Biblio (voir la source) (protégé)
Module:Biblio/Article (voir la source) (semi-protection étendue)
Module:Biblio/Commun (voir la source) (protégé)
Module:Biblio/Lien web (voir la source) (protégé)
Module:Biblio/Ouvrage (voir la source) (semi-protection étendue)
Module:Biblio/Références (voir la source) (protégé)
Module:Catégorisation badges (voir la source) (semi-protection étendue)
Module:Correction syntaxique (voir la source) (semi-protection étendue)
Module:Date (voir la source) (protégé)
Module:Date/Data (voir la source) (semi-protection étendue)
Module:Date complexe (voir la source) (semi-protection étendue)
Module:Fix (voir la source) (semi-protection étendue)
Module:Infobox (voir la source) (semi-protection étendue)
Module:Infobox/Algorithme (modifier)
Module:Infobox/Fonctions (voir la source) (semi-protection étendue)
Module:Infobox/Localdata (voir la source) (semi-protection étendue)
Module:Langue (voir la source) (protégé)
Module:Langue/Data (voir la source) (semi-protection étendue)
Module:Lien interwiki (voir la source) (semi-protection étendue)
Module:Lien interwiki/data catégorisation (voir la source) (semi-protection étendue)
Module:Linguistique (voir la source) (semi-protection étendue)
Module:Nombre2texte (voir la source) (protégé)
Module:Nombre2texte/Data (voir la source) (semi-protection étendue)
Module:Outils (voir la source) (protégé)
Module:P. (voir la source) (protégé)
Module:Palette (voir la source) (semi-protection étendue)
Module:Suivi des biographies (voir la source) (protégé)
Module:Suivi des biographies/données (voir la source) (semi-protection étendue)
Module:TableBuilder (voir la source) (protégé)
Module:Wikidata (voir la source) (semi-protection étendue)
Module:Wikidata/Hiérarchie des langues (voir la source) (semi-protection étendue)
Module:Wikidata/I18n (voir la source) (semi-protection étendue)
Module:Yesno (voir la source) (protégé)

Revenir à la page Tri par tas.

Ce document provient de « https://fr.wikipedia.org/wiki/Tri_par_tas ».