Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Tri par tas

Le tri par tas, utilisé en informatique, est un algorithme de tri qui peut être décrit de la manière suivante :

On fait les hypothèses suivantes : arbre est un tableau et arbre[i] désigne le i-ème élément de ce tableau.

fonction tasser(arbre,max):
debut
 i:=1
 tant que (arbre[i]<arbre[2i] ou arbre[i]<arbre[2i+1]) et i<=max:
 
 debut
 si arbre[i]>arbre[2i+1]:
 echanger arbre[2i] et arbre[i]
 i:=2i
 sinon
 echanger arbre[2i+1] et arbre[i]
 echanger arbre[i] et arbre[2i]
 i:=2i+1
 fin si
 fin tant que
fin fonction

fonction tri_par_tas(arbre):
debut
 pour i:=longueur(arbre) a 2
 debut
 si arbre[i]>arbre[i/2]:
 echanger arbre[i] et arbre[i/2]
 fin si
 fin pour
 # maintenant l'arbre est partiellement trié dans l'ordre décroissant
 pour i:=longueur(arbre) a 2
 debut
 echanger arbre[i] et arbre[1]
 # le premier élément romps l'ordre
 # on restaure l'ordre par la fonction tasser
 tasser(arbre,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.

L'idée qui sous-tend cet algorithme consiste à voir le tableau comme un tas, c'est-à-dire un arbre binaire vérifiant les propriétés suivantes :

• 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.

Les nœuds de l'arbre sont placés dans le tableau ligne par ligne, chaque ligne étant décrite de gauche à droite.

L'algorithme consiste à ordonner partiellement un tableau grâce à une boucle en un temps linéaire (en o(n)) à la fin de laquelle le premier élément du tableau considéré est le plus grand. Puis on échange le premier et le dernier élément à la suite de quoi on appelle la fonction [tasser] sur les éléments précédant le dernier élément du tableau. Puis on réitère l'algorithme sur la partie du tableau qui n'est pas encore triée, c'est-à-dire la partie à gauche du dernier élément. Cet algorithme permet de trier sur place les éléments d'un tableau en un temps moyen équivalent à n.log(n) où n 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.