A Rappels algorithmiques
445
Fig. A.28 Au dessus, le tas
de la figure A.27, après trois
suppressions du minimum (et
en supposant que le minimum
initial était 1) ; en dessous, le
tableau dont la partie de
gauche stocke le tas, et la
partie de droite conserve les
trois premiers minima
successifs en ordre inverse
Tri par tas
Avec les algorithmes d’ajout d’une clé au tas et de suppression du minimum et
réorganisation, il est simple d’obtenir un tri : nous allons d’abord construire un tas
sur place avec les n clés présentes dans le tableau, puis supprimer un à un les minima
successifs du tas, qui est en partie gauche du tableau ; la partie droite servira à garder
les minima successifs, en ordre décroissant de gauche à droite (figure A.28).
Fonction TriTas(tableau T, entier n)
// Précondition : T[1 . . n] est un tableau non trié.
// Postcondition : Retourne le tableau T[1 . . taille] trié en ordre
décroissant.
// Utilise : ajouter, supprimer
// Variables locales : entier taille, élément min
taille = 0
tant que taille < n faire
T, taille = ajouter( T[taille + 1], T, taille)
tant que taille > 1 faire
min, T, taille = supprimer(T, taille)
T[taille + 1] = min
retourner T