Comment trier les objets uniquement sur les relations "moins que"?

Question

dise que j'ai des objets, chacun d'une valeur inconnue et une matrice n par n matrice Z. telle que z (i, j)= 1 si la valeur de l'objet I est inférieure à la valeur de l'objet J, et z (je, j)= 0 sinon.Comment puis-je trier ces n objets, donné seulement la matrice Z?

Answer 1

Ce que vous cherchez est un Tri de comparaison . S'il vous plaît jeter un oeil à cet article.

---

Laissez-nous indiquer clairement l'exigence de deux objets donnés, objet i et objet J quand ils apparaissent dans la liste définitive triée. Objet Je devrais survenir avant l'objet J si z (i, j)= 1. Objet Je peux survenir avant ou après l'objet j si z (i, j)= z (j, i)= 0.

Comme Vonbrand mentionné, nous devrions supposer que la matrice Z spécifie une relation "inférieure à" bien définie ou, en termes de mathématiques, Un ordre strict total sur les valeurs des objets. Sinon, les objets donnés peuvent ne pas être triés.

• z [i, j]= 0 si z [j, i]= 1. Sinon, nous ne pouvons pas trier l'objet i et objet j.
• z [j, i]= 0 si z [i, k]= 1 et z [k, j]= 1 pour certains k. Sinon, nous ne pouvons pas trier l'objet I, J et K (penser à des ciseaux en papier-rock).

---

suppose que z spécifie une relation "inférieure à" bien définie. Ensuite, il définit également une "catégorie $ \ LE $ " opération de comparaison naturellement. Nommément, si z (j, i)= 0, alors objectez i $ \ le $ objet j. Nous pouvons donc appliquer n'importe quel type de comparaison pour trier la N $ N $ Objet.

Presque tous les algorithmes de tri sont des sortes de comparaison. Par exemple, Quicksort, Mergesort, Trier d'insertion, Sélection Trier et Tri de bulles. Une exception notable est Comptage Trier .