Tri par tas

Comme cela a été indiqué dans la section 23.4.3, un tas est un arbre binaire dans lequel chaque élément est inférieur à tous ses descendants (selon un ordre déterminé par l'application). Un tas permet l'insertion d'un élément arbitraire et la suppression d'un élément sur une place connue avec une complexité $O(\texttt{log}n)$.

Ce fait nous donne une idée simple d'algorithme de tri. On suppose que les objets à trier sont initialement dans un ensemble quelconque. Le résultat doit être une séquence triée par ordre croissant (déterminé par une fonction passée en argument). La technique comporte deux étapes.

Dans la première étape, l'ensemble initial est parcouru dans un ordre quelconque et chaque élément est inséré dans un tas initialement vide. Le résultat de cette étape est donc un tas dont la racine (le premier élément de la représentation sous la forme de vecteur) est le plus petit élément (ou l'un des plus petits éléments).

Dans la deuxième étape, une séquence, initialement vide, est créée à partir des éléments du tas obtenu dans la première étape. Le premier élément de la séquence est la racine du tas, puis la racine du tas est supprimée. Cela donne un nouveau tas, la nouvelle racine du tas étant le second élément dans l'ordre, car il est le plus petit parmi les éléments restants. L'opération est répétée tant que le tas n'est pas vide.

Bien que cette méthode marche, elle n'est pas très économique en terme d'espace mémoire. Traditionnellement, les algorithmes de tri utilisent un vecteur qui contient les éléments à la fois avant et après le tri. Ces algorithmes utilisent très peu de mémoire supplémentaire. Clairement, la méthode décrite ci-dessus ne remplit pas ces conditions. Voici une méthode qui évite ce problème et qu'on appelle le tri par tas (en Anglais : heapsort).

Pour cette méthode, on observe qu'un vecteur peut être le codage d'un tas (voir section 23.4.3). On devrait donc pouvoir utiliser le vecteur à trier comme le codage du tas lui-même. Puis, on observe qu'un préfixe arbitraire du vecteur est aussi un codage pour un tas. Pour la création du tas initial à partir du vecteur, il suffit alors de maintenir une frontière mentale dans le vecteur avec le tas à gauche et les éléments non encore insérés à droite. Pour chaque insertion, la frontière est avancée un pas à droite, puis l'élément ainsi inséré est échangé avec son parent pour obtenir un tas (cette méthode est expliquée dans la section 23.4.3). Pour des raisons qui sont expliquées par la suite, la comparaison inverse de celle qui a été fournie pour le tri sera utilisée. Le premier élément du tas sera donc le plus grand d'après l'ordre fourni. La figure 24.1 montre la construction d'un tas à partir d'un vecteur initial.

Figure 24.1: Construction d'un tas à partir d'un vecteur

Une fois le tas construit, il faut alors, de façon itérative, supprimer le premier élément du tas pour construire le vecteur final trié. Cette fois ci, au lieu de construire un vecteur supplémentaire, nous allons déplacer notre frontière à gauche et mettre l'élément supprimé à droite de la frontière. c'est-à-dire, au lieu de simplement déplacer le dernier élément du vecteur représentant le tas, et le mettre au début, nous allons échanger le premier et le dernier éléments. De cette manière, puisque le tas est organisé à l'envers, nous allons déplacer le plus grand élément à chaque itération et le mettre à la fin. La figure 24.2 montre cette opération à partir du tas obtenu dans la figure 24.1.

Figure 24.2: Suppression successive du premier élément

On obtient ainsi un vecteur trié. En ce qui concerne le code, il est difficile de réutiliser les fonctions définies dans la section 23.4.3, car elles dépendent de la modification dynamique de la taille du vecteur, alors que dans le cas du tri par tas, la taille est fixe.

Voici le code :

tripartas.lisp

Ce code dépend du fait que la séquence à trier permet un accès direct aux éléments du vecteur. Il n'est donc pas envisageable d'utiliser le tri par tas avec une liste.

La complexité du tri par tas est clairement $O(n \texttt{log} n)$. Il y a deux boucles séparées. Chacune consiste en une boucle de durée $O(\texttt{log} n)$ imbriquée dans une boucle de durée $O(n)$.

Non seulement le tri par tas est un algorithme de complexité $O(n\texttt{log} n)$ mais la constante multiplicative est aussi relativement faible. Curieusement, le tri par tas est très rapide lorsque le vecteur initial est trié à l'envers. Dans ce cas, la première étape est linéaire, car un vecteur trié à l'envers est déjà un tas. La boucle imbriquée fera dans ce cas une seule itération à chaque fois.