Pb en java

Signaler
Messages postés
14
Date d'inscription
jeudi 9 janvier 2003
Statut
Membre
Dernière intervention
29 avril 2003
-
Messages postés
261
Date d'inscription
jeudi 5 septembre 2002
Statut
Membre
Dernière intervention
6 octobre 2005
-
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 ?

7 réponses

Messages postés
261
Date d'inscription
jeudi 5 septembre 2002
Statut
Membre
Dernière intervention
6 octobre 2005
11
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
Messages postés
14
Date d'inscription
jeudi 9 janvier 2003
Statut
Membre
Dernière intervention
29 avril 2003

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 ?
Messages postés
261
Date d'inscription
jeudi 5 septembre 2002
Statut
Membre
Dernière intervention
6 octobre 2005
11
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
Messages postés
14
Date d'inscription
jeudi 9 janvier 2003
Statut
Membre
Dernière intervention
29 avril 2003

Ouai, mais avec les AVL comment tu fais?
Il faut regarder dans les fils gauv=che et droit et tout non ?
Messages postés
261
Date d'inscription
jeudi 5 septembre 2002
Statut
Membre
Dernière intervention
6 octobre 2005
11
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
Messages postés
14
Date d'inscription
jeudi 9 janvier 2003
Statut
Membre
Dernière intervention
29 avril 2003

Il est non trié, et il faut que je le trie
Messages postés
261
Date d'inscription
jeudi 5 septembre 2002
Statut
Membre
Dernière intervention
6 octobre 2005
11
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