Discussion :

[dionisos56]

bonjour,
voila j'ai un tableau de couple de pointeur sur des objets A
les couples servent a decrire un relation d'ordre entre 2 objets A



ex:

tab[0]=(A1,A3)
tab[1]=(A4,A2)
tab[2]=(A3,A4)
tab[3]=(A10,A3)
( c'est pas du c++ parce que cetait juste pour l'explication, mais sinon j'veut le faire en c++)

equivaut a:

A1>A3
A4>A2
A3>A4
A10>A3

j'aimerai trouver un algoritme qui permette de ranger dans l'ordre decroissant dans un tableau tout les objets que contient le tableau de couple.
en temp O(N) si possible, O(N²) au pire; O(N^3) au encore pire.

(si jamais l'ordre d'un element par rapport a l'autre ne peut pas etre determiner a l'aide du tableau de couple, alors l'ordre entre ces elements n'a pas d'importance)

j'voudrai soit un algoritme tout fait, soit des pistes pour resoudre mon probleme parce je seche un peut.

merci.

[Médinoc]

Alors déjà, tu n'auras rien en O(N). Le temps minimal d'un tri, à moins de circonstances exceptionnelles, est O(N*Log(N)).

Ensuite, avec une organisation creuse comme celle-ci, je ne vois pas trop comment aller en dessous de O(N²).

Selon moi, pour éviter O(N^3), il faudra user un peu de mémoire pour construire une matrice de qui est supérieur à qui (en espérant qu'il soit possible de construire ladite matrice en O(N^2).

Une fois la matrice construire, un algo de tri simple utilisant la matrice comme fonction de comparaison devrait faire l'affaire...

Ou bien, tu peux chercher à chaque fois en temps réel, ou encore essayer un truc du genre "construire le graphe et tenter une variante de parcours en largeur", etc...
Au moins l'avantage qu'il y aurait à construire le graphe, c'est que cela permettrait de s'assurer qu'il est sans cycle...

[dionisos56]

merci pour la reponse, meme si j'suis pas sur d'avoir bien interpreter s'que vous avez voulu dire,
en tout cas voila s'que j'pense faire actuellement:

-recuperer un tableau de tout les elements
-ranger le tableau(grace a la relation de comparaison des pointeurs)
-eliminer les doublons
=> temp O(N*log(N))

-pour chaque element du tableau, indiquer tout les elements auquel il est directement superieur(a l'aide d'une matrice par exemple)
-puis les ranger
=>N*O(N*log(N))=O(N^2*log(N))

utiliser un algoritme de trie classique, avec comme fonction de comparaison R.
R(b,c) cherche dans la premiere colonne de la matrice l'objet b, puis parcourt la ligne ou l'objet b a ete trouver pour voir si l'objet si trouve, si il si trouve: R(b,c)=true
=> O(N*log(N))*O(N*log(N))=O(N²*log²(N))
soit O(N^3*log^3(N)) pour faire le trie de tout les elements entre eux

par contre si il trouve pas c, alors la j'voi pas de methode un peut pret potable pour verifier si un des elements auquel il est superieur n'est pas superieur a c.

en gros j'voi toujour pas dutout comment faire quelque chose de potable.

ps: oubliez s'que j'ai dit, enfaite O(N^3) sa sera pas mal enfaite

[dionisos56]

bon finalement j'ai trouver une solution pas trop mal en temp O(N^3).
j'met parce que j'pense pas que sa soit possible de trouver beaucoup mieu enfaite. ( mais bon, si vous penser l'contraire sa m'interesse pas mal).