Discussion :

[kheraud]

Bonjour,

Je cherche à trier des objets de cette nature :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
                  IDENTIFIANT      NOM      ID_PERE
Object1 :            1           Chips        2
Object2 :            2           Paquet       3
Object3 :            3           Armoire       
Object4 :            4           Sel          3
Object5 :            5           Evier
Object6 :            6           Vaisselle    5

Ces objets sont dans un tableau sur lequel j'itère ligne après ligne.

J'aimerais pouvoir réorganiser ce tableau afin qu'il devienne ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
                  IDENTIFIANT      NOM      ID_PERE
Object3 :            3           Armoire       
Object2 :            2           Paquet       3
Object1 :            1           Chips        2
Object4 :            4           Sel          3
Object5 :            5           Evier
Object6 :            6           Vaisselle    5

Le classement des différents noeuds de même niveau étant fait par ordre alphabétique.

On m'a parlé d'arbres orientés verticalement, je ne comprends pas trop avec ce qu'il y a sur Internet comment utiliser cela.
> Dans l'hypothèse ou ce genre de traitement serait classique, connaitriez-vous une URL, un algorithme courant pour trier mon tableau ?

Merci par avance !

PS : désolé je suis débutant en terme d'algorithmique

K.

[Graffito]

J'aimerais pouvoir réorganiser ce tableau afin qu'il devienne ainsi :

Je n'ai pas saisi la logique de cette réorganisation.
Trier suppose une fonction de comparaison, quelle est-elle ?

[pseudocode]

Je n'ai pas saisi la logique de cette réorganisation.
Trier suppose une fonction de comparaison, quelle est-elle ?

Je suppose qu'il veut qu'un objet "parent" soit listé avant ses "enfants"

[Graffito]

Je suppose qu'il veut qu'un objet "parent" soit listé avant ses "enfants"

Mais, c'est bien sur : la vaisselle dans l'évier !

Si ID_PERE est vide , la clé de tri vaut [NOM , ""].
Sinon, la clé de tri vaut [NOM correspondant à ID_PERE , NOM].

Reste à calculer pour chaque ligne une clé, puis trier les lignes suivant les clés.

[kheraud]

Merci pour vos réponses !!

Si je comprends bien, dans mon exemple cela va donner :

Object1 : [Paquet, Chips]
Object2 : [Armoire, Paquet]
Object3 : [Armoire, ]
Object4 : [Armoire, Sel]
Object5 : [Evier, ]
Object6 : [Evier, Vaisselle]

Puis je classe alphabétiquement selon Clé1 puis Clé2 :
Object3 : [Armoire, ]
Object2 : [Armoire, Paquet]
Object4 : [Armoire, Sel]
Object5 : [Evier, ]
Object6 : [Evier, Vaisselle]
Object1 : [Paquet, Chips]

Peut-être que je me trompe, mais en faisant comme conseillé, l'objet "Chips" n'est pas sous l'objet "Paquet"....

> Est-ce ma manière de comparer ?

Merci pour votre aide !!

K.

[Graffito]

On peut juste généraliser la clé comme un n-uple :
[Nom de l'ancêtre sans ID_PERE, ..., NOM du grand-père, NOM du père correspondant à ID_PERE, NOM]

Mais, la solution la plus appropriée serait de construire un arbre en traitant chaque élément du tableau initial et en le raccodrant à son père et en l'insérant à saplace (ordre alphabétique dans la liste de ses frères).
Ensuite, parcours d'arbre depuis la racine virtuelle à la quelle on aura rattaché tous les éléments sans pères.