2.6 Tri_Tas.java

//////////////////////////////////////////////////////////////
//                                                          //
//             MODULE DE STRUCTURES DE DONNEES              //
//                                                          //
//                ALGORITHMES DE TRI PAR TAS                //
//                                                          //
// Cette classe derive la la classe abstraite               //
//    Algorithmes_Tri et implemente le tri par tas          //
// Note: la liste est la representation d'un arbre parfait  //
//    premiere etape: on le rend partiellement ordonne      //
//    deuxieme etape: on extrait les elements en conservant //
//        la propriete partiellement ordonne                //
// preconditions                                            //
//    ordonner (a):                                         //
//    a /= vide implique (g(a) = vide implique d(a) = vide) //
// proprietes fonctionnelles                                //
//    ordonner(a) =                                         //
//        si a = vide ou a = <o, vide, vide> alors a        //
//        sinon soit a = <o, <o1, gg, dd>, d>;              //
//            si o>=o1 et (d=vide ou o>=racine(d)) alors a  //
//            sinsi o<o1 et (d=vide ou o1>=racine(d)) alors //
//                <o1, ordonner(<o, gg, dd>), d>            //
//            sinon soit a = <o, g, <o2, dg, dd>>;          //
//                <o2, g, ordonner(<o, dg, dd>)>            //
//    tri-sel-iter(l1, l) =                                 //
//        si l = listevide alors l1                         //
//        sinon tri-sel-iter(max(l)::l1, supprimer-max(l))  //
//        fsi                                               //
//    tri (l) = tri-sel-iter(listevide, l)                  //
//                                                          //
// Auteur: Christian CARREZ,                                //
// Institution: CNAM 292 rue Saint Martin, 75141 Paris 03   //
// Derniere modification: 17 fevrier 2000                   //
//////////////////////////////////////////////////////////////

package Demonstration_Tri;

import java.awt.*; 
import Commun_Demonstration.*;

public class Tri_Tas extends Algorithmes_Tri { 
  public Tri_Tas (int[] V_Init, int L_Anim, int H_Anim) { 
    super(V_Init, L_Anim, H_Anim, " tri par tas ");
  } 

  private void Ordonner (int En, int Max) throws StopAnim { 
                           // Ordonner la liste en tas
    int Le_Fils;                        // indice du fils
    int Le_Pere = En;                    // indice du père
    while (2 * Le_Pere <= Max) {            // Il y a un fils
      Le_Fils = 2 * Le_Pere;    // Choisir le plus grand fils
      if (Le_Fils < Max) {                // il a un frère
        Colors[Le_Fils-1] = Color.green;
        Colors[Le_Fils] = Color.green;
        Redessiner();
        if (ieme[Le_Fils-1] < ieme[Le_Fils] ) { 
          Colors[Le_Fils-1] = Color.red;
          Le_Fils = Le_Fils + 1;            // qui est plus grand
        } else Colors[Le_Fils] = Color.red; 
      };
      Colors[Le_Fils-1] = Color.green;
      Redessiner();
      Colors[Le_Fils-1] = Color.red;
      if (ieme[Le_Fils-1] < Valeur_U) break;        // bien placé
      ieme[Le_Pere-1] = ieme[Le_Fils-1]; ieme[Le_Fils-1] = 0;
      Redessiner();
      Le_Pere = Le_Fils; // remonter le fils et poursuivre dessous
    } 
    ieme[Le_Pere-1] = Valeur_U; Valeur_U = 0;       // place finale
    Redessiner();
  } 

  void Le_Tri () throws StopAnim { 
                                       // tri par tas proprement dit
    int K;                                   // construction du tas
    for (K = ieme.length/2; K >= 1; K--) {
      Valeur_U = ieme[K-1]; ieme[K-1] = 0; 
      Colors[K-1] = Color.blue;
      Redessiner();
      Ordonner (K, ieme.length); 
      Colors[K-1] = Color.red; 
      controleDemo.FinEtape() ;
    } 
                                         // extraction du tas
    for (K = ieme.length; K >= 2; K--) {
      Valeur_U = ieme[K-1]; ieme[K-1] = 0;      // dernière feuille
      Redessiner();
      ieme[K-1] = ieme[0]; ieme[0] = 0;
      Colors[K-1] = Color.blue;
      Redessiner();              // le plus grand dans le résultat
      Ordonner (1, K - 1);
              // ordonner avec la dernière feuille à la racine
      Colors[K-1] = Color.red; 
      controleDemo.FinEtape() ;
    } 
    Redessiner();
  } 
}