La transitivité est-elle requise pour un algorithme de tri

Est-il possible d'utiliser un algorithme de tri avec une comparaison non transitive, et si oui, pourquoi la transitivité est-elle répertoriée comme exigence pour le tri des comparateurs?

Contexte:

• Un algorithme de tri trie généralement les éléments d'une liste selon une fonction de comparaison C (x, y), avec

  $$\begin{array}{ll} C(x,y) = \begin{cases} -1 & {\text{if}}\ x\prec y \\ 0 & {\text{if}}\ x\sim y \\ +1 & {\text{if}}\ x\succ y \\ \end{cases} \end{array}$$

  Les exigences pour ce comparateur sont, pour autant que je les comprenne:

  • réflexif: $\forall x: C(x,x)=0$
  • antisymétrique: $\forall x,y: C(x,y) = - C(y,x)$
  • transitive: $\forall x,y,z, a: C(x,y)=a \land C(y,z)=a \Rightarrow C(x,z)=a$
  • C (x, y) est défini pour tous les x et y, et les résultats dépendent uniquement de x et y

  (Ces exigences sont toujours répertoriées différemment selon les différentes implémentations, donc je ne suis pas sûr de les avoir bien comprises)

Maintenant, je me pose des questions sur une fonction de comparaison "tolérante", qui accepte les nombres x, y comme similaires si : C ( x , y ) = { - 1 si x < y - 1 0 $|x - y| \le 1$

Exemples: les deux [ 1, 2, 3, 4, 5]et [1, 4, 3, 2, 5]sont correctement triés par ordre croissant selon le comparateur tolérant ( $C(x,y) \le 0$ si x vient avant y dans la liste)
mais [1, 4, 2, 3, 5]ne l'est pas, puisque C (4,2) = 1

Ce comparateur tolérant est réflexif et antisymétrique, mais pas transitif.

c'est-à-dire C (1,2) = 0, c (2,3) = 0, mais C (1,3) = -1, violant la transitivité

Pourtant, je ne peux penser à aucun algorithme de tri qui ne parviendrait pas à produire une sortie "correctement triée" si l'on donnait ce comparateur et une liste aléatoire.

La transitivité n'est-elle donc pas requise dans ce cas? Et est - il une version moins stricte de transitivité qui est nécessaire pour le tri au travail?

Questions connexes:

• Pourquoi l'antisymétrie est-elle nécessaire pour le tri par comparaison? (sur l'antisymétrie)
• Algorithmes de tri qui acceptent un comparateur aléatoire (environ un C aléatoire (x, y))
• OrderBy avec un IComparer non transitif (à propos de l'algorithme de tri c #, par moi)

Vous avez demandé: pouvons-nous exécuter un algorithme de tri, en lui fournissant un comparateur non transitif?

La réponse: bien sûr. Vous pouvez exécuter n'importe quel algorithme avec n'importe quelle entrée.

Cependant, vous connaissez la règle: Garbage In, Garbage Out. Si vous exécutez un algorithme de tri avec un comparateur non transitif, vous pouvez obtenir une sortie non-sens. En particulier, rien ne garantit que la sortie sera "triée" en fonction de votre comparateur. Ainsi, l'exécution d'un algorithme de tri avec un comparateur non transitif ne sera probablement pas utile de la manière que vous espériez probablement.

À titre de contre-exemple, l'exécution du tri par insertion sur la liste d'entrée aide de votre comparateur laisserait la liste inchangée - mais la liste de sortie résultante n'est pas dans l'ordre trié (selon votre comparateur).$[3, 2, 1]$

Étant donné un ensemble d'éléments et une relation d'ordre binaire, la transitivité est nécessaire pour ordonner totalement les éléments. En fait, la transitivité est même nécessaire pour définir un ordre partiel sur les éléments. http://en.m.wikipedia.org/wiki/Total_order

Vous auriez besoin d'une définition beaucoup plus large de ce que signifie "trié" afin de trier les éléments sans transitivité. Il est difficile d'être autonome. Une autre réponse dit "En particulier, il n'y a aucune garantie que la sortie sera" triée "selon votre comparateur." Mais nous pouvons en fait dire quelque chose de beaucoup plus fort. Vous avez la garantie que la sortie n'est pas triée en fonction de votre comparateur.

Supposons que vous disposez d'un comparateur non transitif qui vous indique , et . Quel élément est le plus petit? Peu importe celui que vous choisissez, votre comparateur vous dira qu'un autre élément est plus petit.$a<b$$b<c$$c<a$

Il semble que ce que vous voulez, c'est organiser les éléments de sorte que tous les classements discernables soient corrects, mais les éléments qui sont proches peuvent être considérés comme "indiscernables". Il est possible de concevoir des algorithmes de tri qui fonctionneront avec de telles comparaisons, mais à moins qu'il n'y ait des limites au nombre de comparaisons pouvant signaler que les choses sont indiscernables, il n'y a aucun moyen de les éviter d'avoir besoin de comparaisons N (N-1) / 2. Pour comprendre pourquoi, choisissez un nombre N et tout algorithme de tri qui fait moins de N (N-1) / 2 comparaisons. Remplissez ensuite une liste L [0..N-1], définissez chaque élément L [I] sur I / N et "triez" ce dernier à l'aide de votre comparateur (la valeur minimale sera 0 et la valeur maximale (N-1) / N , la différence sera donc (N-1) / N, qui est inférieure à 1).

Puisqu'il y a N (N-1) / 2 paires d'articles qui peuvent être comparées, et que le tri n'a pas fait autant de comparaisons, il doit y avoir une paire d'articles qui n'a pas été directement comparée les unes aux autres. Remplacez celui qui a fini par être trié d'abord par 1, et l'autre par -1 / N, ramenez tous les éléments à leur position initiale et répétez l'opération de tri. Chaque opération de comparaison unique donnera zéro, tout comme elle l'a fait la première fois, de sorte que les mêmes comparaisons seront effectuées et les éléments se retrouveront dans la même séquence. Pour que la liste soit correctement triée, le "1" devrait trier après le "-1 / N" (car ils diffèrent de plus d'un), mais puisque l'algorithme de tri ne comparerait jamais ces deux éléments directement l'un avec l'autre, il n'aurait aucun moyen de le savoir.

Remplissez un tableau de n éléments avec les valeurs n, n-1, n-2, ..., 2, 1. Ensuite, essayez de trier en utilisant l'algorithme "d'insertion directe". Vous constaterez que chaque élément est considéré comme égal à l'élément juste avant lui et qu'il n'est donc pas déplacé. Le résultat du "tri" est le même tableau.