Ist für einen Sortieralgorithmus eine Transitivität erforderlich?

Ist es möglich, einen Sortieralgorithmus mit einem nicht-transitiven Vergleich zu verwenden, und wenn ja, warum wird die Transitivität als Voraussetzung für das Sortieren von Komparatoren aufgeführt?

Hintergrund:

• Ein Sortieralgorithmus sortiert im Allgemeinen die Elemente einer Liste nach einer Komparatorfunktion C (x, y) mit

  $$\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}$$

  Die Anforderungen an diesen Komparator sind, soweit ich sie verstehe:

  • reflexiv: $\forall x: C(x,x)=0$
  • antisymmetrisch: $\forall x,y: C(x,y) = - C(y,x)$
  • transitiv: $\forall x,y,z, a: C(x,y)=a \land C(y,z)=a \Rightarrow C(x,z)=a$
  • C (x, y) ist für alle x und y definiert und die Ergebnisse hängen nur von x und y ab

  (Diese Anforderungen werden in den verschiedenen Implementierungen immer unterschiedlich aufgeführt, daher bin ich mir nicht sicher, ob sie in Ordnung sind.)

Jetzt wundere ich mich über eine "tolerante" Komparatorfunktion, die Zahlen x, y als ähnlich akzeptiert, wenn : C ( x , y ) = { - 1 wenn x < y - 1 0 wenn | x - y | ≤ 1 + 1, wenn x > y + $|x - y| \le 1$

[ 1, 2, 3, 4, 5][1, 4, 3, 2, 5]$C(x,y) \le 0$
[1, 4, 2, 3, 5]

Dieser tolerante Komparator ist reflexiv und antisymmetrisch, aber nicht transitiv.

dh C (1,2) = 0, c (2,3) = 0, aber C (1,3) = -1, was die Transitivität verletzt

Ich kann mir jedoch keinen Sortieralgorithmus vorstellen, der mit diesem Komparator und einer zufälligen Liste keine "korrekt sortierte" Ausgabe erzeugen würde.

Ist in diesem Fall also keine Transitivität erforderlich? Und gibt es eine weniger strenge Version der Transitivität, die erforderlich ist , damit die Sortierung funktioniert?

Verwandte Fragen:

• Warum ist für die Vergleichssortierung eine Antisymmetrie erforderlich? (über Antisymmetrie)
• Sortieralgorithmen, die einen zufälligen Komparator akzeptieren (über ein zufälliges C (x, y))
• OrderBy mit einem nicht-transitiven IComparer (über den C # -Sortieralgorithmus , von mir)

Sie fragten: Können wir einen Sortieralgorithmus ausführen, der einen nicht-transitiven Komparator liefert?

Die Antwort: Natürlich. Sie können jeden Algorithmus mit jeder Eingabe ausführen.

Sie kennen jedoch die Regel: Garbage In, Garbage Out. Wenn Sie einen Sortieralgorithmus mit einem nicht-transitiven Komparator ausführen, erhalten Sie möglicherweise eine Unsinnausgabe. Insbesondere kann nicht garantiert werden, dass die Ausgabe nach Ihrem Komparator "sortiert" wird. Die Ausführung eines Sortieralgorithmus mit einem nicht-transitiven Komparator ist daher wahrscheinlich nicht so nützlich, wie Sie es sich erhofft haben.

$[3, 2, 1]$

Bei einer gegebenen Menge von Elementen und einer binären Ordnungsbeziehung ist Transitivität erforderlich, um die Elemente vollständig zu ordnen. Tatsächlich ist Transitivität sogar erforderlich, um eine Teilreihenfolge für die Elemente zu definieren. http://en.m.wikipedia.org/wiki/Total_order

Um Elemente ohne Transitivität zu sortieren, müsste viel umfassender definiert werden, was "sortiert" bedeutet. Es ist schwer, selbstbeständig zu sein. In einer anderen Antwort heißt es: "Insbesondere gibt es keine Garantie dafür, dass die Ausgabe nach Ihrem Komparator 'sortiert' wird." Aber wir können tatsächlich etwas viel Stärkeres sagen. Sie haben die Garantie, dass die Ausgabe nicht nach Ihrem Komparator sortiert ist .

Angenommen, Sie haben einen nicht-transitiven Komparator, der Ihnen sagt $a<b$$b<c$$c<a$

Es hört sich so an, als ob Sie Elemente so anordnen möchten, dass alle erkennbaren Rangfolgen korrekt sind. Objekte, die sich in der Nähe befinden, können jedoch als "nicht unterscheidbar" betrachtet werden. Es ist möglich, Sortieralgorithmen zu entwerfen, die mit solchen Vergleichen funktionieren. Wenn jedoch nicht begrenzt ist, wie viele Vergleiche angeben, dass Dinge nicht unterscheidbar sind, können Sie nicht vermeiden, dass sie N (N-1) / 2-Vergleiche erfordern. Um zu verstehen, warum, wählen Sie eine Zahl N und einen Sortieralgorithmus, der weniger als N (N-1) / 2 Vergleiche durchführt. Füllen Sie dann eine Liste L [0..N-1] aus, setzen Sie jedes Element L [I] auf I / N und "sortieren" Sie es mit Ihrem Komparator (der minimale Wert ist 0 und der maximale (N-1) / N , so wird der Unterschied (N-1) / N sein, was weniger als 1 ist).

Da es N (N-1) / 2 Paare von Gegenständen gibt, die verglichen werden können, und die Sortierung nicht so viele Vergleiche durchgeführt hat, muss es ein Paar von Gegenständen geben, die nicht direkt miteinander verglichen wurden. Ersetzen Sie denjenigen, der zuerst nach 1 sortiert wurde, und den anderen durch -1 / N, setzen Sie alle Elemente auf ihre ursprüngliche Position zurück und wiederholen Sie den Sortiervorgang. Jede einzelne Vergleichsoperation ergibt wie beim ersten Mal Null, sodass dieselben Vergleiche durchgeführt werden und die Elemente in derselben Reihenfolge enden. Damit die Liste korrekt sortiert werden kann, muss die "1" nach "-1 / N" sortiert werden (da sie sich um mehr als eins unterscheiden), da der Sortieralgorithmus diese beiden Elemente jedoch niemals direkt miteinander vergleicht Ich hätte keine Möglichkeit, das zu wissen.

Füllen Sie ein Array von n Elementen mit den Werten n, n-1, n-2, ..., 2, 1. Versuchen Sie dann, mit dem Algorithmus "gerade Einfügung" zu sortieren. Sie werden feststellen, dass jedes Element dem Element unmittelbar davor entspricht und daher nicht verschoben wird. Das Ergebnis der "Sortierung" ist das gleiche Array.