Pb en java

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 ?

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

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 ?



-------------------------------
Réponse au message :
-------------------------------

> 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

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

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



-------------------------------
Réponse au message :
-------------------------------

> 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

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

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



-------------------------------
Réponse au message :
-------------------------------

> 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

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