Aller au contenu

Tri par tas

Un article de Wikipédia, l'encyclopédie libre.
Tri par tas
Une exécution de l'algorithme du tri par tas (Heapsort) trie une partie des valeurs permutées au hasard. Dans un premier temps, les éléments sont réarrangés pour respecter les conditions de tas. Avant le tri à proprement parler, la structure de l'arbre en tas est montrée brièvement par l'illustration.
Découvreur ou inventeur
J. W. J. Williams (en)Voir et modifier les données sur Wikidata
Date de découverte
Problème lié
Structure des données
À l'origine de
Complexité en temps
Pire cas
Voir et modifier les données sur Wikidata
Moyenne
Voir et modifier les données sur Wikidata
Meilleur cas
Voir et modifier les données sur Wikidata
Complexité en espace
Pire cas
Voir et modifier les données sur Wikidata
Animation montrant le fonctionnement du tri par tas (Heapsort).

En informatique, le tri par tas (en anglais heapsort) est un algorithme de tri par comparaisons. Cet algorithme est de complexité asymptotiquement optimale[1]. Sa complexité est proportionnelle à 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 )[2]. 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é de tri n'est pas en général préservé.

Son inconvénient majeur est sa lenteur comparé au tri rapide (qui est 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. nécessaire].

Le tri par tas a été trouvé par J. W. J. Williams (en) en 1964[3]. Il y introduit la structure de 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[4],[5].

C'est un tri par file de priorité utilisant le tas comme file de priorité. Il tire particulièrement avantage de la suppression de clef en et la création du tas à partir d'un tableau en [6].

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 e élément a pour enfants les éléments et si l'indexation se fait à partir de 1 ( et si l'indexation se fait à partir de 0). Si le tableau n'est pas de taille , les branches ne se finissent pas toutes à la même profondeur.

Dans l'algorithme, on cherche à obtenir un 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)[7] :

  • 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 sont les éléments d'indices et (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 et un indice . En supposant que les deux sous-arbres soient des tas et que soit plus petit que ses deux enfants, le rôle de l'opération de tamisage consiste à échanger avec le plus grand de ses fils, et ainsi de suite récursivement jusqu'à ce qu'il soit à sa place[8].

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[9],[10].

La racine de ce tas est donc la valeur maximale du tableau, on l'échange avec est la longueur de . On veut alors que 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é[11].

Pseudo-code

[modifier | modifier le code]
Application de l'algorithme.

On fait l'hypothèse que l'arbre est un tableau indexé entre 1 et longueur, arbre[i] désigne le ième é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 triParTas le tableau arbre est trié suivant l'ordre croissant. Il suffit d'inverser les opérateurs de comparaison pour obtenir un tri dans l'ordre décroissant.

Cet algorithme permet de trier sur place les éléments d'un tableau en un temps de l'ordre de , où 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[12]. 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

[modifier | modifier le code]
  • Quand le tableau est déjà trié, le tri par tas le mélange d'abord avant de le retrier. L'algorithme Smoothsort[13] a pour but de pallier cet inconvénient. Comme le tri par tas, la complexité dans le pire des cas est en mais en si la liste est presque trié. Cependant la complexité moyenne reste en , et en raison de sa complexité il est rarement utilisé[réf. nécessaire].
  • À la fin du tri par tas, pour les 15 derniers éléments environ, l'algorithme effectue plusieurs fois de suite les mêmes inversions, ce qui est inutile[réf. nécessaire]. 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

[modifier | modifier le code]

Notes et références

[modifier | modifier le code]

Sur les autres projets Wikimedia :

  1. C'est-à-dire que l'on démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure.
  2. Cormen et al. 2004, p. 121.
  3. J. W. J. Williams 1964.
  4. Robert W. Floyd 1964.
  5. (en) Peter Brass, Advanced data structures, Cambrige University Press, , 474 p. (ISBN 978-0-521-88037-4, OCLC 221147457, DOI 10.1017/CBO9780511800191 Accès payant), p. 208
  6. François Schwarzentruber, « File de priorité et tas binaire » Accès libre [PDF], (consulté le )
  7. Cormen et al. 2004, p. 121-123.
  8. Cormen et al. 2004, p. 124-125.
  9. On peut même commencer à longueur[A]/2, car chaque nœud après est une feuille donc déjà un tas.
  10. Cormen et al. 2004, p. 126-128.
  11. Cormen et al. 2004, p. 129.
  12. The Analysis of Heapsort, Schaffer R. and Sedgewick R., 2002.
  13. (en) Edsger W. Dijkstra, Smoothsort, an alternative for sorting in situ, Center for American History, Université du Texas à Austin (no 796-a), 16 p. (lire en ligne Accès libre)

Bibliographie

[modifier | modifier le code]

Document utilisé pour la rédaction de l’article : document utilisé comme source pour la rédaction de cet article.

  • (en) J. W. J. Williams, « Algorithm 232 – Heapsort », Communications of the ACM, vol. 7, no 6,‎ (DOI 10.1145/512274.512284 Accès libre)
  • (en) Robert W. Floyd, « Algorithm 245 – Treesort 3 », Communications of the ACM, vol. 7, no 12,‎ (DOI 10.1145/355588.365103 Accès libre, S2CID 52864987)
  • (en) Donald Ervin Knuth, The Art of Computer Programming, vol. 3 : Sorting and searching, Addison-Wesley, , 2e éd., 780 p. (ISBN 978-0-201-89685-5), chap. 5.2.3 (« Sorting by Selection »)
  • Thomas Cormen, Charles Leiserson, Ronald Rivest et Clifford Stein (trad. Georges-Louis Kocher), Introduction à l'algorithmique [« Introduction to algorithms »], Paris, Dunod, , 2e éd. (1re éd. 1990), 1146 p. (ISBN 2-10-003922-9), chap. 6 (« Tri par tas »). Ouvrage utilisé pour la rédaction de l'article