Aide pour algorithme de tri

Bonjour,

Je cherche à trier des objets de cette nature :

Code:

---

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:

---

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.

Citation:

---

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 ?

Citation:

---

Envoyé par Graffito

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" ;)

Citation:

---

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

---

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

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.

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.

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.