CPGE OUJDA SPE

Tri Maximier (tri en utilisant un arbre binaire)

Cette méthode de tri (aussi appelée "tri par tas" ou "heapsort" ou "tri de Williams") est basée sur la notion de tas. Un tas est un arbre binaire parfait tel que l’information contenue dans tout nœud est supérieure à celle contenue dans ses fils. La méthode du tri par tas comporte deux étapes :

1. Construction par insertions successives d’un tas à partir du vecteur à trier.

2. On remplace la racine, qui est nécessairement le plus grand élément du tableau par son fils le plus grand. La racine est transférée à la place de la dernière feuille de l’arbre et celle-ci est repositionnée. On réitère avec la nouvelle racine autant de fois qu’il y a de nœuds dans l’arbre.

Exemple

5

7

3

8

12

6

Par exemple, le tableau ci-dessus devra être vu ainsi :

Représentation en arbre

Si l'on est rendu au nœud numéro n (indice dans le tableau initial), ses deux feuilles porteront les numéros 2n et 2n+1.

L'arbre n'est pas trié pour autant. Pour cela nous devrons le tamiser, c'est-à-dire prendre un nombre et lui faire descendre l'arbre jusqu'à ce que les nombres en dessous lui soient inférieurs. Pour l'exemple, nous allons tamiser le premier nœud (le 5).

Arbre avant tamisage de la racine

En dessous de lui se trouvent deux nœuds : 7 et 3. On choisit le plus grand des deux : 7. Comme 7 est plus grand que 5, on les inverse.

Après une première phase de tamisage de la racine

On recommence : les deux nœuds situés en dessous sont 8 et 12. Le plus grand est 12. Comme 12 est plus grand que 5, on les inverse.

Arbre après tamisage de la racine

Pour trier notre arbre par tas, nous allons le tamiser en commençant, non pas par la racine de l'arbre, mais par les derniers nœuds (en commençant par la fin en quelque sorte). Bien sûr, il est inutile de tamiser les feuilles de l'arbre : elles ne descendront pas plus bas ! Pour limiter les tests inutiles, nous commencerons par tamiser le 3, puis le 7 et enfin le 5. Du coup, nous ne tamiserons que la moitié des nœuds de l'arbre. Faites l'essai, cela devrait vous donner ceci :

Tamisage complet de l'arbre

Plus on descend dans l'arbre plus les nombres sont petits, mais c'est pas trié pour autant ?!

En effet. il reste encore une étape. Nous allons parcourir notre arbre en sens inverse encore une fois. Nous allons échanger le dernier nœud de notre arbre tamisé (le 3) avec le premier (le 12) qui est également le plus grand nombre le l'arbre.

Échange du dernier et du premier nœud

Une fois cet échange effectué, nous allons tamiser notre nouvelle racine, en considérant que la dernière feuille ne fait plus partie de l'arbre (elle est correctement placée désormais). Ce qui devrait nous donner le résultat suivant (voir la figure suivante).

Retamisage de l'arbre privé du 12

Cette manœuvre a ainsi pour but de placer sur la dernière feuille, le nombre le plus grand, tout en gardant un sous-arbre qui soit tamisé. Il faut ensuite répéter cette manœuvre avec l'avant-dernière feuille, puis l'avant-avant-dernière feuille… Jusqu'à arriver à la deuxième (et oui, inutile d'échanger la racine avec elle-même). Nous devrions ainsi obtenir le résultat suivant (voir la figure suivante).

Arbre trié

Cette fois, l'arbre est trié dans le bon ordre.

Mise en œuvre

il nous faut une procédure tamiser, en plus de notre fonction Tri_tas.. pour passer d'un nœud n à celui du dessous, il faut multiplier n par 2 (pour accéder au nœud en dessous à gauche) et éventuellement lui ajouter 1 (pour accéder à celui en dessous à droite).

Algorithme :

fonction tamiser(arbre, nœud, n) :

(* descend arbre[nœud] à sa place, sans dépasser l'indice n *)

k := nœud

j := 2k+1

tant que j ≤ n-1

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+1

sinon

terminer

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

En Python :

def faire_tas(tab, debut, n):

# transforme le tableau "tab" en un tas

racine = debut

while racine*2 + 1 < n:

fils = racine*2 + 1

if fils < n-1 and tab[fils] < tab[fils+1]:

fils += 1

if tab[racine] < tab[fils]:

tab[racine], tab[fils] = tab[fils], tab[racine]

racine = fils

else:

return

def tripartas(tab):

n = len(tab)

debut = n//2 - 1

fin = n - 1

while debut >= 0:

faire_tas(tab, debut, n)

debut -= 1

while fin > 0:

tab[fin], tab[0] = tab[0], tab[fin]

faire_tas(tab, 0, fin)

fin -= 1

return tab

L=[2,7,4,8,0,3,6,5,10]

L=tripartas(L)

print(L)Complexité

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