Pb en java

Question

Je n'arrive pas à trouver comment faire un tri rapide en java sur les avl dont les noeuds et les feuilles sont des vecteurs.
Pouvez-vous m'aider ?

JHelp · Answer

Si tu as un critétère qui te dit si un vecteur est avant un autre, alors implémente Comparable, définit la méthode :
int compareTo(Object objet) 
avec ce critére.
compareTo doit renvoyer : 
->  un entier négatif si l'instance est avant l'objet
->  0 si l'instance est égale à l'objet
->  un entier positif si l'instance est aprés l'objet

Ensuite, tu peux utiliser un TreeSet(java.util), ou une autre classe du package java.util, ou faire ton tri toi même.

JHelp

cs_rayy · Answer

Merci de m'avoir répondu, mais c'est faire le tri moi-meme que j'arrive pas à faire!
As-tu une solution pour moi stp ?

JHelp · Answer

Bon, c'est plutôt un pb d'algo.
  Donc je suppose, que tu utilises le critére que je t'ai donné. C'est à dire une classe qui implémente compareTo.
  Je suppose également, quau départ tes éléments ne sont pas triés.
  Remarque, on peut également faire une liste qui trie au fur et à mesure, mais je ne crois pas que celà soit ton sujet.
  Donc pour le trie rapide, tu peux faire :


  public void tri(Comparable[] elements)
  {
    //Si le tableau est null,on a rien à faire
    if(elements==null)
      return;
    //On récupére la taille du tableau
    int taille=elements.length;
    //Si la taille est inférieur à 2, on a rien à faire
    if(taille<2)
      return;
    //On appel le tri rapide, on va trié tout le tableau
    triRapide(elements,0,taille-1);
  }

//On trie le tableau entre les indice depart et fin inclus
  private void triRapide(Comparable[] elements,int depart,int fin)
  {
     //On calcul l'écart d'indice
    int ecart=fin-depart;
    //Si on a un écart <2 , rien à faire
    if(ecart<2)
       return;
    //Si l'écart est de deux, on inverse si nécessaire)
    if(ecart==2)
    {
        //Si le premier élément est avant le secon, on a rien à faire
        if(elements[depart].compareTo(elements[fin])<=0)
           return;
        //On inverse les éléments
        Comparable element=elements[depart];
        elements[depart]=elements[fin];
        elements[fin]=element;
        return;
     }
    //On prend le premier élément comme pivot
    Comparable pivot=elements[depart];
    //On permute les éléments que tous les éléments inférieurs au pivot soit avant lui, et les supérieurs aprés lui
    //rang ou se trouve le pivot
    int rang=depart;
    //indice de parcourt du tableau
    int indice=depart+1;
    //on va parcourir tous les éléments
    do
    {
      //Si l'élément courant est avant le pivot
      if(elements[indice].compareTo(pivot)<=0)
      {
        //On met l'élément courant à la place du pivot
        elements[rang]=elements[indice];
        //Le pivot sera décalé d'un rang
        rang++;
       //On met l'élément se trouvant à la nouvelle place du pivot, à la place d'où se trouvait l'élément courant
        elements[indice]=elements[rang];
      }
      //on passe à l'indice suivant
      indice++;
    }while(indice<=fin);
    //On place le pivot au rang calculer
    elements[rang]=pivot;
    //On tri la demi partie inférieure au pivot du tableau
    triRapide(elements,depart,rang-1);
    //On tri la demi partie supérieure au pivot du tableau
    triRapide(elements,rang+1,fin);
  }


J'éspére que ça t'aidera

JHelp

cs_rayy · Answer

Ouai, mais avec les AVL comment tu fais?
Il faut regarder dans les fils gauv=che et droit et tout  non ?

JHelp · Answer

Que sont les AVL, des arbres bianaires ou des arbres à nombre de branches quelconques.
Qu'entends-tu par trié des AVL ?
As tu un AVL non trié au départ et tu dois en générer un trié ?
Ou te suffit-il qu'il soit trié ou fur et à mesure ?
S'il s'agit d'un arbre binaire trié au fur et à mesure à équilibre, regade dans les sources, tu trouveras une des miennes qui parle de ce sujet.
JHelp

cs_rayy · Answer

Il est non trié, et il faut que je le trie

JHelp · Answer

Mettons que ton AVL, s'appel Arbre


public void tri(Arbre arbre)
{
   //Si l'arbre est null on a rien a trier
   if(arbre==null)
     return;
   //Si l'arbre  est vide, ou est une feuille, on a rien à trier
   if(arbre.estVide()||arbre.estFeuille())   
     return;
   boolean b=false;
   do    
   {
       b=false;
       tri(arbre.getFilsGauche());
       tri(arbre.getFilsDroit());
       if(arbre.getFilsGauche()!=null)
         if(arbre.getValeur().compareTo(arbre.getFilsGauche())<=0)
         {
            Object o=arbre.getValeur();
            arbre.setValeur(arbre.getFilsGauche().getValeur());
            arbre.setValeur(o);
            b=true;
         }
       if(arbre.getFilsDroit()!=null)
         if(arbre.getValeur().compareTo(arbre.getFilsDroit())>0)
         {
            Object o=arbre.getValeur();
            arbre.setValeur(arbre.getFilsDroit().getValeur());
            arbre.setValeur(o);
            b=true;
         }
    }while(b);
}


JHelp

Pb en java

7 réponses

Votre réponse

Discussions similaires