Une classe
Java solution du problème :
Les 3 sous programmes Java implantant l'algorithme de tri par arbre
:
Notons que l'opérateur booléen optimisé '&&'
évite l'effet de bord lorsque j<1 (c-à-d ici j = 0 ).
Il n'est donc pas necessaire de mettre une sentinelle dans tas[0], puisque
dès j vaut 0 le reste de l'expression n'est pas évaluée
!
Une classe complète permettant l'exécution des sous-programmes
précédents :
class ApplicationTriHeapSort {
static int[] table
= new int[21] ; // le tableau
à trier : 21 éléments
static int max = 19; //
les cellules utiles vont de 1 à 19.(de 1 à table.length-1)
static int[] TabInit = new int[max+1]
; // les données initiales dans
un tableau
static int[] tas = new int[max+1]
; // le tas, la cellule tas[0] peut
contenir une sentinelle
static int[] TabTrie = new int[max+1]
; // le tableau une fois trié
static int P, Lemin; |
static void AfficherTable
( int[] table
) {
// Affichage du tableau
sans les sentinelles
int
n = table.length-1;
for
(
int
i = 1; i <= n; i++)
System.out.print(table[i]+"
, ");
System.out.println();
}
static void InitTable
( ) {
// remplissage aléatoire
du tableau
int
n = table.length-1;
for
( int i = 1; i <= n; i++)
TabInit[i] = (int)(Math.random()*100);
TabInit[0]
= -Integer.MAX_VALUE;// sentinelle non
utilisée ici
}
static void main(String[ ] args)
{
InitTable ( );
System.out.println("Tableau
initial :");
AfficherTable (TabInit
);
Tri_Arbre();
System.out.println("Tableau
une fois trié :");
AfficherTable (TabTrie
);
} |
static void Ajouter
( int x )
{
P++;
int
j = P;
tas[P] = x;
while
( (j > 1)&&
(tas[j] < tas[j / 2]) ) {
int temp = tas[j] ;
tas[j] = tas[j / 2] ;
tas[j / 2] = temp ;
j = j / 2 ;
}
}
static int Supprimer
( )
{
int
Lemini, i ;
Lemini = tas[1] ; // retourne la
racine (minimum actuel) pour stockage éventuel
tas[1] = tas[P] ; // la racine prend la
valeur de la dernière feuille de l'arbre
P = P - 1 ;
int
j = 1 ;
while
(j <= (P / 2)) {
// recherche de l'indice i du plus petit
des descendants de tas[j]
if ((2 * j == P ) | (tas[2
* j] < tas[2 * j + 1])) i = 2 * j ;
else i = 2 * j +1 ;
// Echange éventuel entre tas[j]
et son fils tas[i]
if (tas[j] > tas[i] ) {
int temp = tas[j] ;
tas[j] = tas[i] ;
tas[i] = temp ;
j = i ;
}
else break ;
}
return
Lemini;
}
static void Tri_Arbre()
{
P = 0;
// construction
du tas :
while
(P < max)
Ajouter(TabInit[P+1]);
// appel de l'algorithme Ajouter
// sortie
et élimination des minima successifs :
while
(P >= 1) {
Lemin = Supprimer()
; // appel de l'algorithme Supprimer
TabTrie[max-P] = Lemin ; // stockage du
minimum dans le nouveau tableau
}
} |
} |
Image en diagrammes structurés JGrasp-Like du programme
informations sur les diagrammes
Source
recopiable (cliquez sur le lien)
Tableau initial :
14 , 35 , 84 , 49 , 50 , 94 , 89 , 58 , 61 , 47 , 39 , 58 , 57 , 99
, 12 , 24 , 9 , 81 , 80
Tableau une fois trié :
9 , 12 , 14 , 24 , 35 , 39 , 47 , 49 , 50 , 57 , 58 , 58 , 61 , 80
, 81 , 84 , 89 , 94 , 99
Remonter 