Tri par tas

Un article de Wikipédia, l'encyclopédie libre.

Le tri par tas est un algorithme de tri par comparaisons.

Cet algorithme est de complexité asymptotiquement optimale, c'est-à-dire qu'il est de complexité proportionnelle à n log n où n est la longueur du tableau à trier ; 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.

[modifier] Principe

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.

Un tas peut facilement se représenter par un tableau, en posant que les deux fils de l'élément d'indice n sont les éléments d'indices 2n et 2n + 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. Notons qu'avec cette représentation, les sous-tas (enracinés n'importe où, et finissant n'importe où) sont des sous-tableaux contigus. Toutes les procédures travaillant sur cette représentation des tas s'appliquent donc naturellement aux sous-tas.

L'opération de base du tri par tas 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 A = A[1] dont les deux sous-arbres (A[2] et A[3]) 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 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é.

[modifier] Pseudo-code

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

fonction tamiser(arbre,longueur,nœud):
debut
 i:=nœud
 tant que (arbre[i]<arbre[2i] ou arbre[i]<arbre[2i+1]) et i<=longueur:
  
 début
   si arbre[i]>arbre[2i+1]:
     échanger arbre[2i] et arbre[i]
     i:=2i
   sinon
     échanger arbre[2i+1] et arbre[i]
     échanger arbre[i] et arbre[2i]
     i:=2i+1
   fin si
  fin tant que
fin fonction

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

[modifier] Analyse

Cet algorithme permet de trier sur place les éléments d'un tableau en un temps de l'ordre de dans le pire des cas, 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.

Les algorithmes de tri

à bulle · par sélection · par insertion · par tas · par base · rapide · fusion · comptage · de Shell