Tri par tas 12162 31293713 2008-07-04T12:17:01Z 195.221.193.15 [[Image:Sorting heapsort anim.gif|frame|right|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.]] [[Image:Heap sort example.gif|thumb|300px|Animation montrant le fonctionnement du tri par tas (Heapsort).]] Le '''tri par tas''' est un [[algorithme de tri]] par comparaisons. Cet algorithme est de [[complexité algorithmique|complexité]] asymptotiquement optimale, c'est-à-dire qu'il est de complexité proportionnelle à <math>n \ \log \ n </math> où <math>n</math> est la longueur du tableau à trier ; il n'y a pas de pire des cas en <math>O(n^2)</math> comme avec le [[tri rapide]]. On démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure. Par ailleurs, cet algorithme est ''en place'', c'est-à-dire qu'il ne nécessite pas l'allocation d'une zone mémoire supplémentaire en sus de celle contenant les données d'entrée. L'inconvénient majeur de ce tri est sa lenteur en moyenne comparée au [[tri rapide]]. En effet, le [[tri par tas]] est environ deux fois plus lent dans la plupart des cas. == Principe == L'idée qui sous-tend 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>ième</sup> élément a pour enfants les éléments <math>2n</math> et <math>2n+1</math>. Si le tableau n'est pas de taille <math>2^n</math>, les branches ne se finissent pas tout à fait à 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) : * 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). 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. Une fois le tas de départ obtenu, 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. Plus précisément, considérons un arbre <math>A = A[1]</math> dont les deux sous-arbres (<math>A[2]</math> et <math>A[3]</math>) sont des tas, tandis que la racine est éventuellement plus petite que ses fils. L'opération de tamisage consiste à échanger la racine avec le plus grand de ses fils, et ainsi de suite récursivement jusqu'à ce qu'elle soit à sa place. Pour construire un tas à partir d'un arbre quelconque, on tamise les racines de chaque sous-tas, de bas en haut (par taille croissante) et de droite à gauche. Pour trier un tableau à partir de ces opérations, on commence par le transformer en tas. On échange la racine avec le dernier élément du tableau, et on restreint le tas en ne touchant plus au dernier élément, c'est-à-dire à l'ancienne racine. On tamise la racine dans le nouveau tas, et on répète l'opération sur le tas restreint jusqu'à l'avoir vidé et remplacé par un tableau trié. == Pseudo-code == On fait l'hypothèse que 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 terminer fin si fin tant que fin fonction fonction tri_par_tas(arbre,longueur): pour i:=longueur a 1 tamiser(arbre,i,longueur) fin pour pour i:=longueur a 2 échanger arbre[i] et arbre[1] tamiser(arbre,1,i-1) fin pour fin fonction À la fin de la fonction '''tri_par_tas''' 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. == 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> dans le pire des cas, où <math>n</math> est le nombre d'éléments à trier. 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. == Amélioration possible == * Quand le tableau est déjà trié, le [[tri par tas]] le mélange d'abord avant de le retrier. L'algorithme [[Smoothsort]] a pour but de pallier cet inconvénient. * A 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. 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 1{{er}} et du dernier, du 2{{e}} et de l'avant-dernier etc.) puis effectuer un [[tri par insertion]]. ** ou effectuer un [[tri rapide]] sur les données restantes (on est dans un bon cas avec un tableau à peu près à l'envers), ce qui peut se faire déjà avec les 25 éléments restants == Lien externe == *[http://www.algorithm-code.com/wiki/Heapsort Code de Tri par Tas] {{Algorithme de tri}} [[Catégorie:Algorithme de tri|Tas]] [[cs:Heapsort]] [[de:Heapsort]] [[en:Heapsort]] [[es:Heapsort]] [[he:מיון ערימה]] [[is:Hrúguröðun]] [[it:Heap sort]] [[ja:ヒープソート]] [[lb:Heapsort]] [[lt:Krūvos rikiavimo algoritmas]] [[nl:Heapsort]] [[no:Heapsort]] [[pl:Sortowanie przez kopcowanie]] [[pt:Heapsort]] [[ru:Пирамидальная сортировка]] [[tr:Yığın sıralaması]] [[vi:Sắp xếp vun đống]] [[zh:堆積排序]]