Algorithmique ii - Tri par tas

Présentation de l'algorithme.

Tri d'un tas.

On veut à nouveau trier les valeurs d'un tableau/liste dans l'ordre croissant. Le fonctionnement du tri par tas repose sur des manipulations des nœuds d'un arbre partiellement ordonné. Bien que les arbres soient indispensables pour comprendre ces manipulations, ce tri n'utilise jamais de structure d'arbre pour son implantation mais opère in situ c'est-à-dire sur le tableau/liste fourni(e) en entrée.

On rappelle tout d'abord quelques notions relatives aux arbres (le lecteur est supposé connaître le vocabulaire élémentaire de la théorie des graphes). Pour plus de précision, se référer au cours. Un arbre \(A\) est un graphe \((X,U)\) connexe et sans cycles. Un sommet du graphe est appelé un nœud et un arc est appelé une branche. Le prédécesseur d'un nœud \(x\) (unique, c'est une conséquence de la définition d'un arbre) est appelé le père de \(x\), réciproquement les successeurs d'un nœud \(x\) sont appelés des fils de \(x\). L'arité d'un arbre est le plus grand nombre de fils que peut avoir un nœud de l'arbre.

Un nœud qui n'a pas de fils est appelé une feuille. Un arbre enraciné est un arbre dans lequel il existe un unique nœud qui n'a pas de père, c'est la racine de l'arbre. Il existe un unique chemin qui relie la racine à un nœud quelconque. La profondeur ou hauteur (tout est question de point de vue...) d'un nœud est la longueur du chemin qui le relie à la racine de l'arbre. La profondeur d'un arbre est la longueur du chemin le plus long entre la racine et une feuille. Le nombre de nœuds à la profondeur \(p\) est au plus \(q^p\) si l'arbre est d'arité \(q\). Un arbre de profondeur \(p\) est dit équilibré si tout nœud à une profondeur \(k\) telle que \(k< p - 1\) a exactement \(q^k\) fils. Un arbre peut être muni d'une valuation de ses nœuds (et/ou de ses arcs), c'est-à-dire d'une application \(\nu:X\to{\mathbf R}\).

L'algorithme s'appuie sur une propriété particulière de certains tableaux appelés tas. Pour comprendre ce qu'est un tas, il faut introduire la notion d'arbre partiellement ordonné (en résumé APO).

Un arbre binaire \(A = (X,U)\) de valuation \(\nu\) est partiellement ordonné si et seulement s'il satisfait \begin{equation}\label{eq:apo} \forall x \in X,\qquad \nu(x) \geq \nu(x_g)\ \ \text{et}\ \ \nu(x)\geq \nu(x_d). \end{equation} où \(x_g\) (resp. \(x_d\)) désigne le fils gauche (resp. droit) de \(x\).
Dans la définition, les conditions \(\nu(x) \geq \nu(x_g)\) ou \(\nu(x) \geq \nu(x_d)\) sont supposées satisfaites si le nœud \(x\) n'a pas de fils gauche ou droit. Dans la suite pour alléger les écritures, on confondra un nœud avec sa valuation.

Dans les arbres ci-dessous, l'arbre binaire à gauche est partiellement ordonné mais pas équilibré, l'arbre central est équilibré mais n'est pas partiellement ordonnée, tandis que l'arbre à droite est à la fois équilibré et partiellement ordonné. Les nombres entre les arbres indiquent la profondeur des nœuds dans l'arbre. Notons que les arbres sont représentés à l'envers (racine en haut et feuilles en bas) à cause du sens de lecture qui suit la chronologie de leur construction, celle-ci commençant très souvent par la racine (pour le modèle abstrait tout au moins).

De gauche à droite: Un APO - Un arbre équilibré - Un APO équilibré.

Quand on dispose d'un arbre équilibré valué, on peut le représenter très simplement avec une structure de liste/tableau et réciproquement, il suffit de ranger les valuations des nœuds dans la liste en suivant l'ordre naturel de lecture, de la gauche vers la droite et de haut en bas. Ainsi la liste associée à l'arbre de droite de la figure ci-dessus est \begin{equation}\label{ex:tas} T = [17,12,6,10,9,4,1,2,1,5,3] \end{equation} Un tas est un tableau dont l'arbre associé est un APO. Le tableau ci-dessus est donc un tas.

Dans un tas, la première valeur est la plus grande.

La propriété APO a pour conséquence immédiate que la racine de l'arbre contient la valeur la plus grande, autrement dit la première valeur du tableau est la plus grande. Cette propriété est la clef du fonctionnement du tri par tas. Ce tri ne manipule en réalité qu'une structure de tableau/liste et jamais de structure d'arbre qui ne sert qu'à comprendre les mécanismes de ce tri. Nous allons tout d'abord décrire comment l'algorithme trie un tas. Bien entendu tous les tableaux ne sont pas des tas, mais nous verrons comment transformer un tableau quelconque en tas avec l'algorithme Entasser un peu plus bas.

Le principe est simple et élégant. La plus grande valeur, \(17\) dans notre exemple, étant placé en tête du tas d'après le lemme précédent, il suffit de l'échanger avec la dernière valeur du tableau, ici \(3\), pour qu'elle soit définitivement rangée comme le fait le TriSélection. C'est ce que montre l'arbre de gauche ci-dessous pour le tas \((\ref{ex:tas})\). Après cette transposition, l'arbre n'est plus nécessairement apo (sauf si la valeur qui était dans la dernière cellule du tableau avant l'échange se trouvait être justement la seconde plus grande valeur du tableau).

Restauration de la propriété APO à l'aide de l'al­go­ri­thme Tamiser de \(T = [17,12,6,10,9,4,1,2,1,5,3]\) après échange des valeurs \(3\) et \(17\).

Pour restaurer la propriété APO à la racine, il suffit d'échanger sa valeur avec celle du fils qui contient la plus grande, ici \(12\) (cf. arbre au centre de la figure). On repousse alors le problème sur la racine du sous-arbre où l'on a fait l'échange, ici le sous-arbre gauche, et il suffit de recommencer l'opération jusqu'à ce que la propriété soit rétablie, au pire en rencontrant une feuille. Dans notre exemple, la valeur 3 s'arrête dans sa descente après la transposition avec \(10\) puisque la propriété apo est alors vérifiée. L'opération qui consiste à faire descendre la valeur de la racine dans l'arbre doit bien entendu être réalisée sur le tableau T. Le lecteur démontrera le lemme suivant :

Soit \(i\) l'index d'un nœud d'un arbre binaire équilibré associé à un tableau indexé de \(1\) à \(n\). Alors :
  1. l'index du fils gauche, s'il existe, est égal à \(2i\),
  2. l'index du fils droit, s'il existe, est égal à \(2i+1\),
  3. l'index du père, s'il existe, est égal à \(\lfloor\frac{i}{2}\rfloor\).

Même si nous n'avons pas étudié la récursivité, la nature récurrente de la structure d'arbre et du processus de tamisage est un bon prétexte pour écrire un premier algorithme récursif, en guise d'introduction au cours de troisième année. La simplicité de l'écriture ne devrait pas effrayer outre mesure le lecteur. L'algorithme Tamiser a trois paramètres, le tas, l'index du père et l'index de la dernière cellule à considérer dans le tableau. La base récurrente de l'algorithme consiste à ne rien faire si la propriété APO est satisfaite pour ce nœud. Les premières instructions (#9 à 12) de l'algorithme servent à trouver la valeur k de l'indice du fils avec lequel il faudra faire l'échange, c'est-à-dire le plus grand des deux fils.

Tamiser(@T,ipere,ifin)
données
   T: tableau de valeurs
   ipere: entier
   ifin: entier
variables
   ifils: entier
debut  
   ifils ← 2 * ipere 
   SI ((ifils < ifin) ET (T[ifils+1] > T[ifils])) ALORS 
      ifils ← ifils + 1
   FSI
   SI ((ifils ≤ ifin) ET (T[ipere] < T[ifils])) ALORS 
      Echanger(T,ipere,ifils)
      Tamiser(T,ifils,ifin)
   FSI
FIN

Notons que le troisième paramètre de l'algorithme peut sembler superflu mais sera nécessaire pour faire le tri. La preuve du résultat suivant qui justifie la validité de l'algorithme se fait par récurrence et est laissée au lecteur.

Soit \(A=(X,U)\) un arbre binaire dont les sous-arbres gauche et droit sont des APO. Alors, l'arbre obtenu après l'application de l'algorithme Tamiser à sa racine est un APO.

Le tri d'un tas coule alors de source, l'arbre ayant retrouvé sa propriété APO, la plus grande valeur du tableau est à nouveau en première position et il suffit de l'échanger avec l'avant dernière valeur et de recommencer le processus jusqu'à ce que toutes les plus grandes valeurs aient été rangées à la fin du tableau. Supposons que l'on dispose d'un algorithme Entasser (nous le décrirons plus loin) qui transforme un tableau quelconque en tas, le tri s'écrit facilement:

TriTas(@T)
données
   T: tableau de valeurs
variables
   k: entier
debut  
   Entasser(T)
   k ← #T
   TQ (k > 0) FAIRE
      Echanger(T,1,k)
      Tamiser(T,1,k - 1)
      k ← k - 1
   FTQ 
fin

Conversion d'un tableau en tas.

Il reste à présent à convertir un tableau quelconque \(T\) en tas. Pour celà, il faut rétablir la propriété \((\ref{eq:apo})\) en chaque nœud où elle fait défaut. C'est bien sûr l'algorithme Tamiser qui va être appliqué sur les nœuds en question. On pourrait être tenté de traiter les nœuds dans l'ordre de lecture, donc en commençant par la racine de l'arbre, mais le tableau \(T=[1,3,2,4]\) qui est transformé en \(T=[3,4,2,1]\) et qui n'est pas un tas, convaincra le lecteur que ce n'est pas la bonne approche. Le lemme 3 indique comment procéder. En commençant par le bas, on s'assure ainsi que les sous-arbres gauche et droit sont toujours APO avant d'appliquer l'algorithme. Comme les feuilles sont toujours APO, il est inutile de les tester. Reste alors à déterminer par quel nœud commencer ?

Dans un tableau de taille \(n\) et de premier indice 1 associé à un arbre binaire équilibré, le plus grand indice du nœud qui n'est pas une feuille est égal à \(\lfloor\frac{n}{2}\rfloor\).
L'algorithme Entasser en découle :
Entasser(@T)
données
   T: tableau de valeurs
variables
   i: entier
debut  
   i ← #T / 2
   TQ (i > 0) FAIRE
      Tamiser(T,i,#T)
      i ← i - 1
   FTQ 
fin
Saisissez les valeurs de votre tableau \(T=\,[\)\(]\). Pour que l'af­fi­cha­ge reste lisible, la taille du tableau est limitée à 32 valeurs. Choisissez le délai entre les dif­fé­ren­tes étapes : ms.

Arbre associé à \(T\) durant l'exé­cu­tion de l'al­go­ri­thme TriTas.

Dans les deux phases, quand le tableau \(T\) est transformé en tas puis quand il est trié, le nœud qui va être traité par l'algorithme Tamiser est matérialisé en jaune et gras sur fond rouge. Si la propriété apo est violée, le nœud fils avec lequel il sera échangé est matérialisé en blanc sur fond rouge. Quand le tableau \(T\) retrouve sa propriété de tas, la racine et le dernier nœud qui seront échangés par l'algorithme TriTas sont matérialisés sur fond jaune. Dans ce tableau \(T\), on commence le processus de transformation en tas par le nœud d'indice .

Démontrez le lemme 5. Utilisez le lemme 3.
Écrivez une version itérative de l'algorithme Tamiser.

Complexité

Nous allons estimer la complexité en calculant le nombre de fois où l'on teste la propriété APO qui est la clef du fonctionnement de l'algorithme. Ce nombre de tests permet aisément de déterminer le coût global puisque si la condition est satisfaite il n'y a rien à faire, sinon il faut échanger un père avec l'un de ses fils et dans les deux cas, le coût est constant. Donc un test a une complexité en \(\Theta(1)\).

Commençons par l'algorithme Entasser qui transforme un tableau en tas. Dans le meilleur des cas le tableau est déjà un tas et aucun échange n'a lieu en parcourant les \(\lfloor n/2\rfloor\) premiers nœuds, la complexité est donc \(\check T_{\text{Entasser}}(n)=\Theta(n)\). Dans le pire des cas, chacun des \(\lfloor n/2\rfloor\) premiers nœuds viole la propriété APO et on suppose qu'il va descendre jusqu'à une feuille. La profondeur d'un arbre étant le logarithme du nombre de ses nœuds on pourrait penser que chacun des \(\lfloor n/2\rfloor\) nœuds va faire un chemin de longueur \(\log_2 n\) et conclure que la complexité dans le pire des cas est en \(n\log n\), mais la situation s'avère bien meilleure comme nous allons le montrer. Le lemme suivant va nous être utile:

Montrez qu'un nœud d'indice \(i\) est à la profondeur \(\lfloor \log_2 i\rfloor\). En déduire la hauteur \(h\) d'un arbre binaire équilibré à \(n\) sommets. Montrez que la valeur d'un nœud d'indice \(i\) ne peut descendre à la profondeur \(h\) que si \begin{equation}\label{eq:gd} i\leq\left\lfloor\frac{n}{2^{h-\lfloor\log_2 i\rfloor}}\right\rfloor, \end{equation} et que les autres nœuds ne peuvent descendre qu'à la profondeur \(h-1\).

À la lumière de cet exercice, dans le cas défavorable, la valeur d'un nœud d'indice \(i\) peut descendre jusqu'à une feuille qui est située à la profondeur maximale \(h:=\lfloor\log_2 n\rfloor\) ou en \(h-1\) selon que \(i\) satisfait (\ref{eq:gd}) ou non. Nous pouvons donc majorer le nombre de tests par \((h-\lfloor\log_2 i\rfloor)\) et le minorer par \((h-\lfloor\log_2 i\rfloor-1)\). Nous allons poursuivre ce calcul uniquement pour la majoration, la minoration s'obtenant de la même façon. On écrit \begin{align} \hat T_{\text{Entasser}}(n)&\leq \sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}(h-\lfloor\log_2 i\rfloor)\\ &=\lfloor\frac{n}{2}\rfloor h-\sum_{i=1}^{\lfloor n/2\rfloor}\lfloor\log_2 i\rfloor\\ &\leq \frac{n\log_2n}{2}-\sum_{i=1}^{n/2}\log_2 i\label{eqtas} \end{align} On majore la somme par une intégrale en rappelant que la primitive de \(\ln x\) est \(x\,\ln x -x\): \begin{equation}\label{eq:majint} \sum_{i=1}^{n/2}\log_2 i\leq\frac{1}{\ln 2}\int_{1}^{\frac{n}{2}+1}\ln x\, dx=\frac{1}{\ln 2}\left[x\ln x -x\right]_{1}^{\frac{n}{2}+1}, \end{equation} En injectant ce résultat dans (\ref{eqtas}) et en majorant \(-\log_2(n+2)\) par \(-\log_2n\) et \(\frac{n}{\ln 2}\) par \(n\) on obtient successivement: \begin{align} \hat T_{\text{Entasser}}(n) &\leq \frac{1}{2}\left[n\log_2n-\left((n+2)(\log_2(n+2)-1)-\frac{n}{\ln 2}\right)\right]\\ &=\label{eq:A}\frac{1}{2}\left[n\log_2n-n\log_2(n+2)+n-2\log_2(n+2)+2+\frac{n}{\ln 2}\right]\\ &\label{eq:B}\leq n-\log_2 n+1\\ &=O(n). \end{align} On peut de la même manière obtenir la minoration \(\Omega(n)\) et conclure \[\hat T_{\text{Entasser}}(n)=\Theta(n).\]

Montrez que la complexité dans le pire des cas de l'algorithme TriTas vaut \[\hat T_{\text{TriTas}}(n)=\Theta(n\log n).\]

Notons que l'analyse du meilleur des cas et du cas moyen sont très difficiles et n'ont été obtenus qu'en 1992 par R. Shaeffer et R. Sedgewick et publiés dans The analysis of heapsort, Journal of Algorithms, Vol. 15, #1, pp. 76-100, 1993. Dans les deux cas la complexité est en \(\Theta(n\log n)\) mais le cas moyen est 2 fois plus coûteux que le meilleur des cas.

Travaux pratiques

Attention ! En Python les indices des tableaux commencent à 0, il faut donc adapter toutes les formules des algorithmes.

Écrivez une fonction Tamiser(T,i,n) qui applique l'algorithme de descente du nœud d'indice i dans le sous-arbre associé au sous-tableau T[1,n].
Écrivez une fonction Entasser(T) qui transforme un tableau quelconque en TAS. Écrivez une fonction TriTas(T) qui trie un tableau T à l'aide du tri par tas en utilisant les deux fonctions écrites précédemment.
Vérifiez de manière empirique que la fonction de complexité de l'algorithme du tri par tas dans le cas moyen est \(\hat T(n)=\Theta(n\log n)\). Pour cela, comparez les graphes des fonctions suivantes à l'aide de Gnuplot : la fonction du nombre de comparaisons (uniquement celles liées à l'arbre de décision) selon la taille \(n\) de la liste à trier et la fonction \(n\mapsto n\log n\).

Pour cela, écrivez une fonction GenTab(n) qui renvoie un tableau de taille \(n\) dont les valeurs ont été tirées au hasard. Reprenez cette suggestion pour engendrer une permutation aléatoire.